13
$\begingroup$

I have read in Wikipedia and some other texts that

The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory.

But earlier it is written that the halting problem is an undecidable problem and thus TM can't solve it! Since LBA are defined as a type of TM, should the same not hold for them?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 22 '14 at 4:14

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 9
    $\begingroup$ You can use a TM to determine if a LBA halts on a given input by checking if it halts in, say, O(2^2^n) steps by simulation. Any LBA working for longer than that is stuck in an infinite loop. This isn't saying LBAs can solve the halting problem for general TMs! $\endgroup$ – Yonatan N Mar 22 '14 at 2:55
  • $\begingroup$ Finite automata are also a type of TM. $\endgroup$ – Raphael Mar 22 '14 at 11:33
  • $\begingroup$ @Raphael You cannot edit questions like that. You changed the meaning of the question, thus making my existing answer out of topic, while the other answer was out of topic and is now in topic. $\endgroup$ – babou Mar 22 '14 at 11:39
  • $\begingroup$ @babou I don't see how I changed the meaning of the question, and I don't see how either of the two questions was not answering the question (even though they use different approaches). $\endgroup$ – Raphael Mar 22 '14 at 11:41
  • $\begingroup$ @Rap The original question is more about logical discourse than about formal justification of LBA properties, and that is what you removed from the title. To me it is clear that, though it might be proved that halting is decidable for LBAs, the OP is wondering how it can be compatible with other statements regarding inclusion of LBAs in TMs and undecidability of halting for TMs (can I edit back?). BTW no intent to disparage Yuval's answer. I expect he will get most of the votes, because that is what the readership is after (which is a pedagogical problem in itself), even if I will not indulge. $\endgroup$ – babou Mar 22 '14 at 12:25
18
$\begingroup$

The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is $S$, the alphabet size is $A$, and the number of states is $Q$, then the number of possible configurations is $QSA^S$. If the machine halts then it must halt within $QSA^S$ steps, since otherwise, by the pigeonhole principle, it has a repeated configuration and so is stuck in an infinite loop. Therefore to determine whether the machine halts, we just run it for $QSA^S$ steps and see whether it halts within that time frame.

$\endgroup$
  • $\begingroup$ Why does that argument work for non-deterministic machines? $\endgroup$ – Raphael Mar 22 '14 at 11:36
  • 1
    $\begingroup$ Due to Savitch's theorem. $\endgroup$ – Yuval Filmus Mar 22 '14 at 12:34
  • $\begingroup$ I did not know (or remember) of Savitch's theorem other than the name (I never did much complexity). But I am not sure it can be used that way, as it applies to decision procedures, i.e. halting computations, while decidability of halting is precisely what must be proved. The proof could be adapted to include space-bounded semi-decisions, but it seems simpler to prove separately that halting is decidable for space-bounded TM, thus turning space-bounded semi-decisions into full decisions. This is close to what is done by Hopcroft-Ullman-79 in their lemma 12-1, before proving Savitch's theorem. $\endgroup$ – babou Mar 23 '14 at 18:33
  • 1
    $\begingroup$ I might be me misunderstanding this, but is the answer to literally run the program, and see if it gets stuck in an infinite loop or not? $\endgroup$ – Mikayla Maki Oct 5 '15 at 14:44
  • 1
    $\begingroup$ @TrentonMaki Yea, that's exactly so. $\endgroup$ – Yuval Filmus Oct 5 '15 at 17:13
10
$\begingroup$

You seem stuck with a logical problem.

From the fact that there are books that you cannot read, you cannot infer that you cannot read any book.

Saying that the halting problem is undecidable for Turing Machines (TM) only means that there are machines for which there is no way to determine whether they halt or not by some uniform procedure that will always halt.

However there are Turing Machines that do halt. Now take a subset of Turing Machines, called the Nice Turing Machines (NTM), such that it contains only Turing Machines that do halt if and only if the tape contains an even number of symbols. If a machine M is known to be from that set, you have a simple way to decide whether M will halt: you check whether the number of tape symbols is even (it requires only two fingers).

But that procedure will not work for TM that are not in the NTM set. (too bad!)

So the halting problem is decidable for the NTM, but not for the TM in general, even though the NTM set is included in the TM set.

This is actually critical, and sometimes forgotten, when interpreting undecidability result.

It may well be that one can prove that an important property is undecidable for a very large family of mathematical or computational objects.

This does not mean that you should stop looking for a solution, but only that you will not find one for the whole family.

What you may then do is identify relevant subfamilies for which solving the problem remains important, and try to provide algorithms to decide whether the property holds for members of that smaller family.

Typically, halting is undecidable for TM in general, but it is decidable, often very simply, for large and useful families of automata, which can all be seen as special cases of TM.

$\endgroup$
  • 2
    $\begingroup$ "Saying that the halting problem is undecidable for Turing Machines (TM) only means that there are machines for which there is no way to determine whether they halt or not by some procedure that will always halt." -- Not quite true. For any given TM, the halting problem is decidable. It's the general decision problem that's undecidable, i.e. there is no one algorithm that deals with all TMs. (I think this has to be made very, very clear for beginners. Cf the pi problem.) $\endgroup$ – Raphael Mar 22 '14 at 11:38
  • $\begingroup$ A more immediate example is the set of all TMs that always hold. Your's adds some extra flavor because it lies outside of the normal hierarchy. $\endgroup$ – Raphael Mar 22 '14 at 11:39
  • $\begingroup$ Right. I should have said "uniform procedure", but it was implicit in my mind as I said "procedure that will always halt" implying that I can use it on any input, meaning any machine. But it is true that a procedure could work correctly for one machine, and do anything for other machines. Well ... - - - - - - - - Regarding the second comment, that is what I wrote at first. I then changed my mind because I thought my example would be easier to understand intuitively, as the selection of machines does not rely as directly on the property to be decided (though it is close). $\endgroup$ – babou Mar 22 '14 at 12:02
2
$\begingroup$

In short, A LBA has finite number of configurations, say D. Hence, we can run for D steps and conclude the result. If it runs for more that D steps, by pigeonhole principle, we can say that, it is stuck in an infinite loop.

$\endgroup$
  • 1
    $\begingroup$ What does this add over the existing answer? This seems to just repeat it, in less detail. While I appreciate that you are trying to contribute, we'd prefer that you avoid repeating existing answers and instead focus on answering questions that don't already have a good answer. $\endgroup$ – D.W. Apr 20 at 22:31

Your Answer

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

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