Aquí hay algunos ejemplos de idiomas reconocibles de Turing, en contraste con otras clases de idiomas:
Ejemplos de idiomas reconocibles de Turing:
* El lenguaje de todas las máquinas Turing que se detienen en la cadena vacía: Podemos construir una máquina Turing que simule una máquina Turing dada en la cadena vacía. Si la máquina simulada se detiene, nuestra máquina acepta. Si boques para siempre, nuestra máquina buce para siempre. Esto es reconocible; No hay forma de decir definitivamente una máquina * no * se detendrá.
* El lenguaje de todas las declaraciones verdaderas en la aritmética de primer orden: El teorema de integridad de Gödel muestra que se puede probar cada declaración verdadera. Una máquina Turing puede enumerar sistemáticamente todas las pruebas posibles y aceptar una declaración si se encuentra una prueba. Sin embargo, si una declaración es falsa, la máquina nunca se detendrá.
* El lenguaje de todas las gramáticas sin contexto que generan al menos una cadena de longitud 10: Una máquina Turing puede generar sistemáticamente todas las cadenas de un CFG determinado y verificar su longitud. Si encuentra una de la longitud 10, acepta. Si el CFG no genera tal cadena, la máquina podría ejecutarse indefinidamente tratando de encontrar una.
* El lenguaje de todos los pares de máquinas Turing (M1, M2) de modo que M1 se detiene cuando se le da la codificación de M2 como entrada: Esto ilustra la complejidad. Podemos construir una máquina que simule M1 en la codificación de M2. Si M1 se detiene, nuestra máquina acepta. De lo contrario, se dispara. Esto resalta la indecidabilidad inherente a muchos problemas reconocibles de Turing.
Cómo difieren de otros tipos de idiomas:
La diferencia clave radica en el comportamiento de detención:
* Idiomas decidables (recursivos): Estos son idiomas para los que existe una máquina de turbio que siempre se detiene y decide correctamente si una cadena de entrada dada está en el idioma o no. Cada cadena obtiene una respuesta definitiva de "sí" o "no". Los ejemplos incluyen idiomas regulares, idiomas sin contexto (con algunas restricciones) y muchos otros que pueden decidir algoritmos con terminación garantizada.
* Turing reconocible (recursivamente enumerable) Idiomas: Como se discutió anteriormente, estos idiomas son reconocidos por máquinas Turing que pueden recubrirse para siempre en cadenas no en el idioma. Son un * superconjunto * de idiomas decidables de Turing; Cada lenguaje decidible también es reconocible.
* Idiomas no reconocibles: Estos idiomas ni siquiera pueden ser reconocidos por una máquina Turing. No hay algoritmo, por ineficiente que pueda identificar correctamente todas las cadenas en el idioma. Un ejemplo es el complemento del problema de detención (el lenguaje de todas las máquinas Turing que * no * se detienen en la cadena vacía).
En resumen:
| Clase de idioma | Comportamiento de detención | Ejemplo |
| ------------------------- | ---------------------------------------------------- | --------------------------------------------------------------------
| Turing-Decidable | Siempre se detiene, decide correctamente la membresía | Idiomas regulares, idiomas sin contexto (con restricciones) |
| Turing reconocible | Se detiene y acepta cadenas en el idioma, puede recorrer lo contrario | Lenguaje de máquinas Turing que se detienen en la cadena vacía |
| No reconocible | Ninguna máquina Turing puede reconocerlo | Complemento del problema de detención |
La jerarquía es:Turing decidable ⊂ Turing reconocible ⊂ Todos los idiomas. La inclusión es estricta; Hay idiomas reconocibles que no son decidibles. Y hay muchos idiomas más allá de los reconocibles.