Cualquier propiedad no trivial sobre el lenguaje reconocido por una máquina de Turing es indecidible.
Una propiedad sobre las máquinas de Turing se puede representar como el lenguaje de todas las máquinas de Turing, codificadas como cadenas, que satisfacen esa propiedad. La propiedad P es sobre el lenguaje reconocido por las máquinas de Turing si cada vez que L (M) = L (N) entonces P contiene (la codificación de) M si contiene (la codificación de) N. La propiedad no es trivial si existe al menos una máquina de Turing que tiene la propiedad, y al menos una que no la tiene.
Prueba: sin limitación de generalidad, podemos suponer que una máquina de Turing que reconoce el lenguaje vacío no tiene la propiedad P. Porque si lo tiene, simplemente tome el complemento de P. La indecidibilidad de ese complemento implicaría inmediatamente la indecidibilidad de P.
- ¿Cuáles son los problemas que no podemos resolver debido a los límites de la computación?
- Cómo usar Excel para encontrar la mediana sin usar una función
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
- ¿Qué cursos de matemáticas en la universidad son más importantes para la informática?
- ¿De qué manera es mejor transferir valores variables en JavaScript?
Para llegar a una contradicción, supongamos que P es decidible, es decir, hay una máquina de torneado B que reconoce las descripciones de las máquinas de Turing que satisfacen a P. Usando B podemos construir una máquina de torneado A que acepte el lenguaje {(M, w ) | M es la descripción de una máquina de Turing que acepta la cadena w}. Como el último problema es indecidible, esto mostrará que B no puede existir y que P también debe ser indecidible.
Sea MP una máquina de Turing que satisfaga P (como P no es trivial, debe haber una). Ahora A opera de la siguiente manera:
- En la entrada (M, w), cree una (descripción de a) Máquina de Turing C (M, w) de la siguiente manera: En la entrada x, deje que la máquina de Turing M se ejecute en la cadena w hasta que acepte (así que si no lo hace aceptar C (M, w) se ejecutará para siempre). A continuación, ejecute MP en x. Acepte si MP lo hace. Tenga en cuenta que C (M, w) acepta el mismo lenguaje que MP si M acepta w; C (M, w) acepta el lenguaje vacío si M no acepta w.
Por lo tanto, si M acepta w, la máquina de Turing C (M, w) tiene la propiedad P, y de lo contrario no la tiene. - Alimente la descripción de C (M, w) a B. Si B acepta, acepte la entrada (M, w); si B rechaza, rechaza.
