Una máquina de Turing que vuelve a un estado encontrado anteriormente con su cabeza de lectura / escritura en la misma celda de la misma cinta será atrapada en un bucle. Tal máquina no se detiene.
¿Alguien puede dar un ejemplo de una máquina que nunca se detiene y que no funciona?
x^2
dónde se realizan losx
ciclos entre-100
y100
el ciclo con un módulo y detenerse cuando el resultado es negativo. Podría calcularx%2
dónde x varía de cero a infinito positivo y detenerse cuando el resultado es igual a 2. En lenguaje ensamblador, los bucles do / while / for se reducen con un salto condicional, pero el salto cond solo significa poco.Respuestas:
Considere la TM que siempre mueve el cabezal de la cinta hacia la derecha e imprime un símbolo especial de cinta no en blanco en cada paso. Esto significa que la TM nunca se detiene, ya que siempre se mueve hacia la derecha, y nunca repite un estado, ya que después de k pasos, el cabezal de la cinta está sobre la celda k de la máquina. En consecuencia, cada configuración de la máquina es diferente de todas las demás, y la máquina siempre realiza un bucle.
También podríamos mostrar de manera no constructiva la existencia de tales máquinas. Asuma por contradicción que cada TM que nunca se detiene eventualmente se repite. Esto significa que si inicia un TM en una cadena w , eventualmente sucederá uno de los siguientes:METRO w
En este caso, el problema de detención sería decidible de la siguiente manera. Dada una TM y una cadena w , simule M en w , en cada punto escribiendo el contenido de la cinta, el estado actual y la posición actual de la cinta. Si esta configuración es un duplicado, la salida "no se detiene". De lo contrario, si M se detiene en w , la salida "se detiene". Como se garantiza que uno de estos sucederá eventualmente, este proceso siempre termina, por lo que tendríamos un algoritmo para el problema de detención, que sabemos que no existe.METRO w METRO w METRO w
¡Espero que esto ayude!
fuente
Una máquina de Turing que calcula todos los lugares decimales de π (o cualquier otra fracción no terminante, en cualquier base) nunca se detiene, y se puede hacer que escriba en cada celda solo un número finito de veces. Por supuesto, el hecho de que no haya una transición a un estado de detención sería un regalo muerto, pero al menos es un ejemplo natural.
Un caso más interesante (pero también ambiguo) sería una máquina de Turing que calcula iterativamente la función Collatz en su entrada, terminando si y solo si obtiene el entero 1. La famosa conjetura de Collatz
fuente
pi
. Un TM podría detenerse siempre que el cuadrado de cualquier dígito seapi
igual a exactamente 7.Considere cualquier máquina de Turing que no se detenga y que nunca mueva el cabezal de lectura / escritura hacia la izquierda.
fuente
Si esto fuera cierto, entonces el problema de detención sería decidible. Simplemente registraría cada par (cinta, estado) visto al ejecutar la máquina Turing, y la máquina se detendría (en cuyo caso obviamente se detiene), o verá un par que ha visto antes, en cuyo caso la máquina no se detiene
Dado que el problema de detención es indecidible, esto no puede ser cierto. (Vea otros ejemplos para ejemplos de contador).
fuente