Decidibilidad del lenguaje
Un idioma se llama Decidable o Recursive si hay una máquina de Turing que acepta y se detiene en cada cadena de entrada w. Cada idioma decidible es Turing-Aceptable.
Un problema de decisión P es decidible si el idioma L de todos los casos de sí a P es decidible.
Para un lenguaje decidible, para cada cadena de entrada, la TM se detiene en el estado de aceptación o rechazo como se muestra en el siguiente diagrama:
Ejemplo 1
Descubra si el siguiente problema es decidible o no:
¿Es un número "m" primo?
Solución
Números primos = {2, 3, 5, 7, 11, 13, ………… ..}
Dividir el numero ‘m’ por todos los números entre '2' y '√m' comenzando desde '2'.
Si alguno de estos números produce un resto cero, entonces pasa al "Estado rechazado", de lo contrario, pasa al "Estado aceptado". Entonces, aquí la respuesta podría ser 'Sí' o 'No'.
Hence, it is a decidable problem.
Ejemplo 2
Dado un idioma regular L y cuerda w, ¿cómo podemos comprobar si w ∈ L?
Solución
Tome el DFA que acepta L y comprueba si w es aceptado
Algunos problemas más decidibles son:
- ¿Acepta DFA el idioma vacío?
- ¿Es L 1 ∩ L 2 = ∅ para series regulares?
Note -
Si un idioma L es decidible, entonces su complemento L' también es decidible
Si un idioma es decidible, hay un enumerador para él.