[Solved]: Is the halting problem specific to Turing machines?

Problem Detail: 

The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or produce an output. Not just Turing machines have these characteristics: for example, a linear-bounded automaton can also loop.

So, as well as a proof that you can't use a Turing machine to decide whether a Turing machine will halt, is it not also a proof that you can't use a pushdown automaton to decide whether a pushdown automaton will halt, and so on, for any automaton/language that has the ability to loop?

Asked By : jameshfisher

Answered By : David Richerby

The halting problem applies to any model of computation: you can always ask, "Given this machine and this input for it, does the machine halt?" Indeed, for any two models of computation $A$ and $B$, you can always ask the more general question, "Is there an $A$-machine that, given a description of a $B$-machine and its input, determines whether that machine halts?" Often, we take $A=B$.

What does vary between machine models is decidability of the halting problem. If we say "decidable" on its own, it means Turing-decidable, i.e., model $A$ above is Turing machines. For, e.g., $B$ is DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step. For $B=$Turing machines, the well-known diagonalization argument proves undecidability, and this extends by reduction to any Turing-equivalent model of computation. That is, any model of computation that can simulate and be simulated by Turing machines.

The diagonalization proof has few assumptions – see Wikipedia for more details. There needs to be a coding of machines so they can be used as inputs to the machines themselves and the machines need to be able to simulate an "if" statement, loop forever, return a value, duplicate a value and be closed under subprograms (i.e., the model wouldn't become more powerful if you let machines call each other as subroutines). Therefore, no model of computation that has these properties can decide its own halting problem.

Note that this includes any model that can simulate a Turing machine, even if that model is more powerful. For example, consider the class $H$ of Turing-like machines with an oracle for the Turing machine halting problem. That is, the machines operate just like Turing machines but have a special instruction that can look at the tape and give an immediate yes or no answer to the question, "Does the ordinary Turing machine described there halt on the input described?" Thus, the machines are more strictly powerful than ordinary Turing machines. These oracle machines cannot decide their own halting problem, by the same diagonalization proof as for ordinary Turing machines. In fact, there's a strict, infinite hierarchy of machines: consider machines $H'$ that have an oracle for the $H$-halting probem, and then machines $H''$ with an oracle for the $H$-halting problem and... See Turing degree and the arithmetical hierarchy for more on that.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19231