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 𝑀 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?

$\endgroup$
4
  • $\begingroup$ Yuval Filmus' head banger, again, but writing in at least one state? $\endgroup$
    – greybeard
    Apr 23, 2020 at 4:53
  • $\begingroup$ Yes, it should write in at least one state. $\endgroup$
    – user119566
    Apr 23, 2020 at 6:11
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Apr 23, 2020 at 6:16
  • $\begingroup$ 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? $\endgroup$
    – user119566
    Apr 23, 2020 at 6:36

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.