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

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?

• Yuval Filmus' head banger, again, but writing in at least one state? – greybeard Apr 23 at 4:53
• Yes, it should write in at least one state. – user119566 Apr 23 at 6:11
• Trivially, there are halting machines writing to finite memory. What shall I conclude, adding the above example of a non-halting machine, regarding the significance of writing to finite memory with respect to the Halting problem? – greybeard Apr 23 at 6:16
• If we have a function telling us whether a machine writes to finite memory or not, how can we with this function decide if a machine halts? – user119566 Apr 23 at 6:36

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.