1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

Consider a Turing machine that repeatedly moves its head right, then left, then right, then left, and so on.

$\endgroup$
2
  • $\begingroup$ I didn't think of that! Good example. I'm thinking, could we somehow deduce if a machine halts by knowing it writes to finite memory? $\endgroup$
    – user119566
    Apr 22 '20 at 21:35
  • 1
    $\begingroup$ This sounds like a completely different question. $\endgroup$ Apr 22 '20 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy