0
$\begingroup$

My understanding:

The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way an LBA can loop is by entering a configuration it's already been in, which is easy to check. However, unlike an LBA, a Turing Machine can also loop by entering infinitely many new configurations, none of which accept. So it seems that what the Halting Problem's undecidability really means is that the problem of checking whether a Turing Machine will enter infinitely many new configurations without accepting is undecidable.

My question:

But real computers are LBAs, not TMs. They can't enter infinitely many new configurations. So why is the undecidability of the Halting Problem a useful result?

I've looked at the answers to this and similar questions, and invariably they go something like, "a real computer has a bazillion configurations, and so waiting until you hit a repeat one would take a bazillion years." But as I detailed above, Halting undecidability doesn't seem to tell us anything about that kind of looping; it only tells us about the infinitely-many-new-configurations kind that real computers can never engage in.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Turing machines can also be non-halting by revisiting the same configurations over and over again. The problem is that you don't know when to stop looking for such behavior. $\endgroup$ – Pontus Jun 16 '17 at 6:13
3
$\begingroup$

Detecting whether a Turing machine loops can be arbitrarily difficult. For example, pick any problem P and consider the program:

k = 0
done = False
while not done:
  if <k encodes a solution to P>:
    k = 0
  elif <k encodes a solution to ¬P>:
    break
  else:
    k += 1

This program either terminates or runs forever with repeating configurations, but in order to tell whether configurations repeat, we need to know whether P has a solution. Now just insert a very difficult (undecidable) P.

A real computer has a bazillion configurations. That number is closer to infinity than to any number we can actually comprehend. Turing machines are a better mathematical model of real computers than finite state automata. Something similar happens in physics: the Earth is made from finitely many molecules, but physicists use differential equations that assume matter to be continuous and smooth. That is because the extremely large finite number of molecules is better approximated with the continuum than a discrete system with bazillion states.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "That is because the extremely large finite number of molecules is better approximated with the continuum than a discrete system with bazillion states." -- What does "better" mean here? I assume you mean that we get a tractable model? $\endgroup$ – Raphael♦ Jun 16 '17 at 9:20
  • $\begingroup$ I don't want to be too specific but yes the model is tractable and it is also more useful In addition it has good explanatory power. $\endgroup$ – Andrej Bauer Jun 16 '17 at 10:07
  • $\begingroup$ I guess I stumbled over the apparent claim that the continuous approximation was a better approximation than the discrete, exact description (if there were such a thing). $\endgroup$ – Raphael♦ Jun 16 '17 at 12:08
  • $\begingroup$ "You are mistaken when you say that 'the only way' for a Turing machine to diverge is to "enter infinitely many new configurations'". I didn't say that. In any case, I don't think I phrased my question well. I'll have to think about it some more. $\endgroup$ – Tyler Jun 17 '17 at 2:50
  • $\begingroup$ Sorry, your statement about looping referred to LBA's. I changed my answer. Buy yes, I don't exactly understand what you're asking. Which did not me prevent from answering... $\endgroup$ – Andrej Bauer Jun 17 '17 at 10:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.