Comprender el paisaje primero
Antes de sumergirnos en ejemplos, aclaremos las categorías:
* Idiomas decidables (recursivos): Estos son idiomas para los cuales una máquina Turing puede * siempre * detenerse y responder correctamente "sí" (aceptar) si la cadena de entrada está en el idioma o "no" (rechazar) si la cadena de entrada no está en el idioma. La máquina Turing siempre proporciona una respuesta definitiva.
* Turing reconocible (recursivamente enumerable) Idiomas: Estos son idiomas para los cuales una máquina Turing se detendrá y aceptará si la cadena de entrada * está * en el idioma. Sin embargo, si la cadena de entrada está * no * en el idioma, la máquina Turing podría detenerse y rechazar, o podría ejecutarse para siempre (bucle). La clave es que * eventualmente * dice "sí" para las cuerdas en el idioma.
* Idiomas reconocibles (no recursivamente enumerables): Estos son idiomas para los cuales * No * turing Machine incluso puede diseñarse para reconocer de manera confiable las cuerdas en el idioma. No importa cuán inteligente sea, no puede construir una máquina Turing que acepte todas las cuerdas en el idioma (y potencialmente se detenga cuando no lo sea). El complemento de un lenguaje reconocible de Turing no es reconocible.
Ejemplos de idiomas reconocibles no aturdidos
Los ejemplos más comunes de idiomas reconocibles no aturdidos a menudo implican los complementos de problemas indecidibles bien conocidos.
1. El complemento del problema de detención (¬halt):
* El problema de detención (Halt): Este es el lenguaje que contiene todas las codificaciones de la máquina Turing `⟨m, W⟩` donde la máquina de Turing` M` se detiene en la cadena de entrada `W`. (Esto es reconocible por Turing pero * no * Turing-Decidable).
* ¬halt: Este es el lenguaje que contiene todas las codificaciones de la máquina Turing `⟨m, w⟩` donde la máquina de turing` m` no * no * se detiene en la cadena de entrada `W`.
* Por qué no es reconocible: Si ¬halt fuera reconocible, entonces Halt sería decidable (podríamos simular `M` en` W` y si nuestro reconocimiento para ¬halt acepta, sabemos que `M` no se detiene; si rechaza, sabemos` m 'de alto). Pero Halt está * probado * indecidible. Dado que el detento es reconocible pero no decidable, su complemento, halt, no debe ser reconocible. Si Halt fuera decidible, entonces tanto y su cumplido sería reconocible.
2. El complemento del problema de aceptación (¬A TM ):
* El problema de aceptación (a tm ): Este es el lenguaje que contiene todas las codificaciones de la máquina Turing `⟨m, w⟩` donde la máquina de turing` M` acepta la cadena de entrada `W`. (Esto es reconocible por Turing pero no decidable de Turing).
* ¬A TM : Este es el lenguaje que contiene todas las codificaciones de la máquina Turing `⟨m, W⟩` donde la máquina de turing` m` no * no * acepta la cadena de entrada `W`. `M` puede rechazar o bucle.
* Por qué no es reconocible: Razonamiento similar al de ¬halt. Si ¬A tm eran receptivos a Turing, luego a tm sería decidable, contradiciendo la indecidabilidad conocida de A TM .
3. El complemento del problema de vacío para las máquinas Turing (¬E TM ):
* El problema de vacío (e tm ): Este es el lenguaje que contiene todas las codificaciones de máquina Turing `⟨m⟩` donde el lenguaje reconocido por Turing Machine` M` está vacío (es decir, `l (m) =∅`). (Esto es * no * Turing reconocible).
* ¬E TM : Este es el lenguaje que contiene todas las codificaciones de la máquina Turing `⟨m⟩` donde el lenguaje reconocido por la máquina de Turing` m` no es * no vacía (es decir, `l (m) ≠ ∅`).
* Por qué es reconocible a Turing: Una máquina de Turing puede reconocer este idioma simulando la máquina `m` en todas las entradas posibles hasta que` m` acepte.
4. El lenguaje de las máquinas Turing que no se detienen en * ninguna * entrada:
* Considere el lenguaje de las máquinas Turing que, cuando se inicia * cualquier cadena de entrada * *, nunca se detendrá. No hay un algoritmo general para determinar esto.
* Puede intentar ejecutar la máquina en muchas entradas diferentes, pero nunca se asegurará de que no se detendrá en alguna otra entrada no probada.
Cómo difieren los idiomas reconocibles no aturdidos
La diferencia clave radica en la capacidad de crear una máquina Turing que * de manera confiable * reconoce cadenas en el idioma:
* turing-decidable: Una máquina Turing * siempre * da una respuesta correcta ("sí" o "no") y se detiene.
* Turing reconocible: Una máquina Turing da una respuesta "sí" si la cadena está en el idioma, pero podría recorrer para siempre si la cadena es * no * en el idioma.
* no reconocible: * No* Turing Machine se puede construir para reconocer de manera confiable las cadenas en el idioma. Cualquier máquina de Turing que intente aceptará algunas cadenas que * no * no * en el idioma, se encuentran para siempre en las cuerdas que * están * en el idioma o fallarán de alguna otra manera fundamental.
intuición
Piense en ello así:
* decidible: Tienes una prueba perfectamente confiable que siempre te da la respuesta correcta.
* Reconocible: Tiene una prueba que * definitivamente * dirá "sí" si es la respuesta correcta, pero es posible que no pueda decirle si la respuesta es "no".
* no reconocible: Ni siquiera puede crear una prueba que identifique de manera confiable los casos de "sí". Cualquier prueba que se le ocurra será defectuosa y podría darle resultados incorrectos.
Implicaciones importantes
La existencia de idiomas reconocibles que no son atractivos tienen profundas implicaciones para la informática y las matemáticas:
* Límites de cálculo: Demuestra que hay limitaciones inherentes a lo que las computadoras pueden hacer, sin importar cuán poderosos sean.
* indecidabilidad: Destaca la existencia de problemas que son fundamentalmente indecidibles:no hay un algoritmo que pueda resolverlos en todos los casos.
* Técnicas de prueba: Necesita el uso de técnicas de prueba sofisticadas (como la diagonalización y las reducciones) para demostrar la indecidabilidad o no reconocimiento de ciertos problemas.
En resumen, los idiomas reconocibles no aturdidos definen el límite de lo que es fundamentalmente incomputable. Son una parte crucial para comprender los límites teóricos de la computación.