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.