How can we know if a Turing machine halts, given that it writes to finite memory?

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 𝑀 writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, can we somehow deduce if the machine halts based on if it writes to a finite amount of memory cells?

Link to related post: Turing machines: can a machine write to a finite number of memory cells, but not halt?

Answer 1

To answer your question, if you know that a Turing machine uses only $M$ cells, then you can tell whether it halts by running it for enough steps. If the Turing machine uses only $M$ cells, then it can be in one of $N$ configurations, where $N$ depends on $M$, the number of states, and the alphabet size. If you run it for $N$ steps and it doesn't halt, then altogether it will have gone through $N+1$ configurations, two of which must be equal, hence it is in an infinite loop and won't halt.

However, your actual question is different. You want to show that the following set is undecidable: $$ L = \{ \langle M \rangle \colon M \text{ uses a finite amount of memory} \}. $$ We will do so by reduction from the halting problem. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

for i from 1 to infinity:
    simulate M for one step, and halt if M halts
    move the head i steps to the right
    move the head 2i steps to the left
    move the head i steps to the right
end for

If $M$ halts, then $M'$ also halts, and in particular uses a finite amount of memory. Otherwise, $M'$ will necessarily use an infinite amount of memory.