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!

Was it helpful?

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
scroll top