Aquí hay algunos ejemplos de idiomas indecidibles, que ilustran diferentes formas de indecidabilidad surge:
1. El problema de detención (h):
* Descripción del idioma: H ={⟨m, W⟩ | Turing Machine M se detiene en la entrada W}. Este lenguaje consiste en todos los pares de la codificación de una máquina de Turing (⟨m⟩) y una cadena de entrada (w) de modo que la máquina m se detenga cuando se le da como entrada.
* indecidabilidad: Se ha demostrado que no puede existir ningún algoritmo que determine correctamente, por cada ⟨m, w⟩, si m se detiene en w. Este es un resultado fundamental en la teoría de la computabilidad. Cualquier intento de construir dicho algoritmo conduce a una contradicción (típicamente a través de la diagonalización).
* Por qué es indecidible: La indecidibilidad del problema de detención se deriva de la naturaleza autodeferencial inherente de las máquinas de Turing. Un algoritmo hipotético que resuelve el problema de detención podría usarse para crear una máquina paradójica que contradice su propio comportamiento predicho.
2. El problema de aceptación (a):
* Descripción del idioma: A ={⟨m, w⟩ | Turing Machine M acepta W}. Esto es similar al problema de detención, pero se centra específicamente en la aceptación (la máquina se detiene en un estado de aceptación).
* indecidabilidad: Esto también es indecidible. Si pudiéramos decidir A, también podríamos decidir H (porque si M acepta W, claramente se detiene en W). Dado que H es indecidible, A debe ser indecidible.
3. El problema de vacío para las máquinas Turing (E):
* Descripción del idioma: E ={⟨m⟩ | L (m) =∅} donde L (m) es el lenguaje aceptado por Turing Machine M. Este idioma contiene los codificaciones de todas las máquinas de Turing que no aceptan cadenas (su lenguaje está vacío).
* indecidabilidad: No hay un algoritmo que pueda determinar, para cada máquina de Turing M, si L (M) está vacío. Esto está relacionado con el problema de detención; Si pudiéramos resolver E, podríamos resolver el problema de detención mediante la construcción de una máquina m 'que se detiene si y solo si m se detiene y acepta w.
4. Publicar problema de correspondencia (PCP):
* Descripción del idioma: Este es un ejemplo más complejo que involucra pares de cuerdas. Es indecidible determinar si un conjunto dado de pares de cuerdas tiene una solución (una concatenación de cadenas de los pares que coinciden).
* indecidabilidad: La indecidibilidad de PCP se demuestra utilizando reducciones (que demuestra que si PCP fuera decidible, entonces el problema de detención también sería decidible, una contradicción).
Idiomas decidibles - Contraste:
Idiomas decidibles, por otro lado, * tienen * algoritmos que siempre se detienen y clasifican correctamente las cadenas como pertenecientes al idioma o no. Los ejemplos incluyen:
* El lenguaje de los palíndromos: Un algoritmo puede verificar fácilmente si una cadena dada es la misma hacia adelante y hacia atrás.
* El lenguaje de las cadenas que contiene "ABC": Un algoritmo simple puede escanear una cadena y verificar la subcadena "ABC".
* El lenguaje de las cuerdas binarias de longitud uniforme: Un algoritmo puede verificar la longitud de la cadena.
En esencia, la diferencia se reduce a si un algoritmo puede diseñarse para * siempre * dar una respuesta correcta de sí/no en tiempo finito. Para idiomas indecidibles, este algoritmo es demostrablemente imposible de crear. La existencia de tal algoritmo es la característica definitoria que distingue los idiomas decidibles de los idiomas indecidibles.