Turing machines: can a machine write to a finite number of memory cells, but not halt?
-
29-09-2020 - |
Question
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, is writing to a finite amount of memory cells equivalent to halting, or can there be cases where a machine writes to a finite amount of memory cells without halting?
Thank you in advance!
Solution
Consider a Turing machine that repeatedly moves its head right, then left, then right, then left, and so on.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange