Entonces, se pregunta cómo demostrar que [math] A_ {TM} [/ math] es indecidible usando HALT. Eso es un poco diferente de su declaración de preguntas.
Suponga que tiene una máquina para decidir [matemáticas] A_ {TM} [/ matemáticas]. Sabemos que podemos usar máquinas de Turing para simular otras máquinas de Turing. Así que construyamos uno que ejecute [math] A_ {TM} [/ math] en la entrada [math] \ langle M, w \ rangle [/ math] que obtienes. Luego, a partir de nuestra entrada, construyamos otra máquina [matemática] M ‘[/ matemática] que simule [matemática] M [/ matemática] pero luego invierta la salida, entonces si [matemática] M [/ matemática] devuelve Verdadero, [matemática ] M ‘[/ math] devuelve False, y viceversa. Si [math] M [/ math] no se detiene, tampoco lo hará [math] M ‘[/ math].
Entonces, ahora construimos nuestro solucionador para HALT usando estas piezas: ejecutaremos [math] A_ {TM} [/ math] en [math] \ langle M, w \ rangle [/ math] y [math] \ langle M ‘, w \ rangle [/ math]. Si cualquiera de estos devuelve True, sabemos que [math] M [/ math] se detiene en [math] w [/ math] porque tiene un valor de retorno de True o False. Si devuelve False, sabemos que no puede detenerse, porque no tiene ninguno de los dos posibles valores de retorno. Construir [math] M ‘[/ math] y ejecutar [math] A_ {TM} [/ math] en cada entrada constituyen operaciones de tiempo finito: [math] A_ {TM} [/ math] es una máquina de decisión, así que siempre termina, y nuestra descripción para construir [matemáticas] M ‘[/ matemáticas] también debería hacerlo. Por lo tanto, esto decide HALT, que no puede ser, porque HALT es indecidible. La única suposición que hicimos para llegar aquí fue que [math] A_ {TM} [/ math] existía, por lo que [math] A_ {TM} [/ math] no puede existir.
- ¿Es necesaria la inteligencia artificial para convertirse en desarrollador de juegos?
- ¿Cómo funciona SB Game Hacker?
- ¿Cuál es una explicación simple del algoritmo Earley?
- ¿Podré obtener CSC o ECE en VIT con un rango de 54k en la categoría B?
- Si tengo un año para ser realmente bueno en programación algorítmica y todavía no he probado suerte en programación competitiva, ¿cuál debería ser mi enfoque?
