Turing Machines: une machine peut-elle écrire sur un nombre fini de cellules de mémoire, mais pas arrêter?

Question

J'essaie de réduire le problème d'arrêt pour montrer un autre problème est indéciable.Le problème implique un programme qui est vrai si une machine $ M $ écrit à une quantité arbitraire de mémoire et false si elle écrit à une quantité finie de cellules de mémoire.Je pense maintenant, écrit à une quantité finie de cellules de mémoire équivalentes à l'arrêt, ou peut-il y avoir des cas où une machine écrit une quantité finie de cellules de mémoire sans arrêt?

Merci d'avance!

Answer 1

Considérons une machine de Turing qui déplace à plusieurs reprises sa tête à droite, puis à gauche, puis à droite, puis à gauche, et ainsi de suite.