Capacidad de resolución del idioma

Capacidad de resolución del idioma

El idioma se llama Soluble o Recursivo si hay una máquina de Turing que toma y se detiene en cada línea de entrada w… Todos los idiomas decidibles son aceptables para Turing.

Problema de solución PAG solucionable si el idioma L de todos los casos si PAG soluble.

Para un lenguaje que se puede resolver, para cada línea de entrada, TM se detiene en un estado de aceptación o rechazo, como se muestra en el siguiente diagrama:

Ejemplo 1

Descubra si el siguiente problema tiene solución:

¿Es m primo?

Decisión

Números primos = {2, 3, 5, 7, 11, 13, …………..}

Dividir el numero ‘metro’ todos los números de «2» a «√m», comenzando con «2».

Si alguno de estos números da un resto cero, pasa al estado «Rechazado»; de lo contrario, pasa al estado «Aceptado». Entonces, aquí podría responder «sí» o «no».

Por lo tanto, este es un problema con solución.

Ejemplo 2

Dado un lenguaje ordinario L y la linea w¿Cómo podemos comprobar si w ∈ L?

Decisión

Tome el DFA que acepta L y comprueba si w recibió

Algunos problemas más solucionables:

• ¿Acepta DFA lenguaje vacío?
• L1 ∩ L2 = ∅ para series regulares?

Nota –

• Si el idioma L es solucionable, entonces su complemento L ‘ también solucionable

• Si el idioma se puede resolver, hay un enumerador para él.