patternMajor
Why is the halting problem decidable for LBA?
Viewed 0 times
problemwhythehaltingdecidableforlba
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#22925, answer score: 22
Revisions (0)
No revisions yet.