Como se señala a continuación, el conjunto de todas las cadenas de longitud 2014 es un lenguaje regular y, por lo tanto, decidible.
Sin embargo, si entiendo la pregunta correctamente, se está refiriendo a un problema de determinar el lenguaje L sobre el alfabeto binario de manera que:
L = {: M es una máquina de Turing y M acepta una cadena de longitud 2014}
- ¿Algún consejo para estudiar la complejidad del espacio para programar entrevistas? ¿Cuáles son algunos buenos recursos para aprender sobre la complejidad del espacio?
- ¿Es esto un tipo de selección?
- ¿Dónde puedo encontrar problemas difíciles de algoritmo / estructura de datos?
- ¿Cuál es la forma correcta de escribir un algoritmo? ¿Podemos usar la sintaxis del lenguaje en el que estamos escribiendo?
- ¿Cuál es la relación entre el índice de una matriz y el tamaño de una matriz?
Ahora, este lenguaje es indecidible.
es decir, no existe ninguna máquina de Turing ( M-2014 ) de manera que, dada otra máquina de Turing M , decida si M acepta una cadena de longitud 2014
Prueba:
Suponga que L es decidible y existe un M-2014 [matemáticas] [/ matemáticas] que puede decidirlo. Luego, M-2014 puede usarse como un submódulo para crear un HALT decisivo para resolver el problema de detención de la siguiente manera:
Bosquejo de prueba:
Podemos construir un decisor para el problema de detención para cualquier máquina de Turing M y la cadena de entrada w creando otro programa dinámico que acepte una cadena (ficticia) d y haga 2 cosas:
- Ejecuta M (w)
- Aceptar
Tenga en cuenta que este programa rojo que creamos en realidad no utiliza M (w) y solo calcula M (w) y luego pasa instantáneamente al estado de aceptación. Observe también que acepta cualquier cadena (incluidas las de longitud 2014) si y solo si M (w) se detiene. De lo contrario, si M (w) no se detiene, el programa rojo nunca pasa al estado de aceptación y, por lo tanto, no acepta ninguna cadena.
Este nuevo programa rojo que acabamos de crear se introduce en nuestra caja negra M-2014 [matemática]. [/ Math] Si nuestra caja negra dice que nuestro programa rojo acepta cadenas de longitud 2014, es decir, acepta, entonces M (w) debe haberse detenido y si el cuadro negro rechaza, entonces M (w) no se detiene.
(Tenga en cuenta que el programa rojo nunca se ejecuta realmente, sino que solo se envía como entrada al cuadro negro mágico)
Por lo tanto, dada la caja negra M-2014 que decide L , entonces podemos decidir fácilmente el problema de detención. Pero sabemos que el problema de detención es indecidible, por lo tanto, por contradicción, M-2014 no puede existir.
