Est-ce qu'une machine sans arrêt boucle toujours?

Une machine de Turing qui revient à un état rencontré précédemment avec sa tête de lecture / écriture sur la même cellule de la même bande exacte sera prise en boucle. Une telle machine ne s'arrête pas.

Quelqu'un peut-il donner un exemple d'une machine sans arrêt qui ne boucle pas?

Considérez le TM qui déplace toujours la tête de bande vers la droite et imprime un symbole de bande spécial non vierge à chaque étape. Cela signifie que la TM ne s'arrête jamais, car elle se déplace toujours vers la droite et ne répète jamais un état, car après k pas, la tête de bande se trouve au-dessus de la kème cellule de la machine. Par conséquent, chaque configuration de la machine est différente de toutes les autres et la machine boucle toujours.

Nous pourrions également montrer de manière non constructive l'existence de telles machines. Supposons par contradiction que chaque MT qui ne s'arrête jamais finit par une boucle. Cela signifie que si vous démarrez un TM sur une chaîne w , l'un des événements suivants se produira finalement:$M$$w$

1. s'arrête, ou$M$
2. répète une configuration.$M$

Dans ce cas, le problème d'arrêt serait décidable comme suit. Étant donné un TM et une chaîne w , simulez M sur w , en écrivant à chaque point le contenu de la bande, l'état actuel et la position actuelle de la bande. Si cette configuration est un doublon, la sortie "ne s'arrête pas". Sinon, si M s'arrête sur w , sortez "s'arrête". Étant donné que l'un d'eux est garanti de se produire à terme, ce processus se termine toujours, nous aurions donc un algorithme pour le problème d'arrêt, dont nous savons qu'il n'existe pas.$M$$w$$M$$w$$M$$w$

J'espère que cela t'aides!

Une machine de Turing qui calcule toutes les décimales de π (ou toute autre fraction non terminale, dans n'importe quelle base) ne s'arrête jamais, et peut être faite pour écrire sur chaque cellule seulement un nombre fini de fois. Bien sûr, le fait qu'il n'y ait pas de transition vers un état d'arrêt serait un cadeau mort, mais c'est au moins un exemple naturel.

Un cas plus intéressant (mais aussi ambigu) serait une machine de Turing qui calcule itérativement la fonction Collatz sur son entrée, terminant si et seulement s'il obtient l'entier 1. La fameuse conjecture de Collatz

$$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$$ est que pour toute entrée, cette procédure s'arrête finalement. Mais on ne sait pas si c'est le cas. Il peut échouer de deux manières différentes, en principe: soit il peut trouver une séquence d'entiers qui boucle (correspondant à l'existence d'un entier n tel que pour un certain nombre de compositions, où n  ≠ 1); ou il pourrait y avoir des chaînes d'entiers n , f (n) , f (f (n))$f \circ f \circ \cdots f(n) = n$, ... qui divergent asymptotiquement vers l'infini. Si des séquences de ce dernier type existent, cela impliquerait que la machine de Turing que j'ai décrite ci-dessus ne se répéterait pas, car la bande serait continuellement changée en nombres de plus en plus grands.

Considérez toute machine Turing sans arrêt qui ne déplace jamais la tête de lecture / écriture vers la gauche.

Si cela était vrai, le problème de l'arrêt serait décidable. Vous enregistrez simplement chaque paire (bande, état) vue lors de l'exécution de la machine Turing, et la machine s'arrête (dans ce cas, elle s'arrête évidemment), ou vous voyez une paire que vous avez déjà vue, auquel cas la machine ne s'arrête pas.

Étant donné que le problème de l'arrêt est indécidable, cela ne peut pas être vrai. (Voir d'autres exemples pour des contre-exemples.)