6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A recursive language is one, for which there exists a TM which decides it. By the Church Turing Thesis: A language is said to be "computable" iff it is recursive. The thesis is responsible for the definition of the word "computable". All other computational models can be simulated by a TM, but the opposite is not be true (for example an FSM). Intuitively, a TM is the strongest computational model and hence any proof that a language cannot be "computed" must come by disproving the language to be recursive. $\endgroup$ – swarnim_narayan Dec 24 '13 at 6:11
  • $\begingroup$ When you say there are no assumptions in proving "Undecidability of the Halting Problem", you miss out on the fact that it is "a proof by the Church Turing Thesis" (Robert Soare uses this exact phrase) $\endgroup$ – swarnim_narayan Dec 24 '13 at 6:12
  • 1
    $\begingroup$ @swarnim_narayan You can't prove anything "by the Church-Turing thesis" because it's not a statement of mathematics (or, at best, it's a definition of what constitutes a "reasonable" model of computation). Sure, you can prove the halting problem for any Turing-equivalent model of computation by reduction to the halting problem for Turing machines but that's not using Church-Turing. Church-Turing just says that you probably don't care about any model of computation that isn't Turing-equivalent. $\endgroup$ – David Richerby Dec 24 '13 at 10:24
  • $\begingroup$ Thanks for the explanation. Please do let me know if I'm misinterpreting the book but in the first chapter of "RE Sets and Degrees", Soare states explicity that he would use the phrase "proof by Church's Thesis" when a T.M. would have to be constructed for showing decidability of some set. Infact a lot of formal proofs in the chapter use statements like "$\psi$ is partially recursive by Church's Thesis" (Where $\psi$ is a function). $\endgroup$ – swarnim_narayan Dec 24 '13 at 14:57
  • 1
    $\begingroup$ The diagonalization technique used in the usual proof of the Halting Problem can be modified to other types of machines. However, all the proof shows for less powerful models of computation is that (say) a PDA cannot decide whether a PDA halts -- in some sense this is not surprising. $\endgroup$ – András Salamon Dec 25 '13 at 21:47
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the difference between being "closed under subprograms" and "call[ing] each other as subroutines"? $\endgroup$ – babou Jul 28 '15 at 12:13
  • $\begingroup$ @babou I don't think there's a difference, is there? My phrasing suggests that I was explaining the phrase "closed under subprograms" as meaning programs "call[ing] each other as subroutines". $\endgroup$ – David Richerby Jul 28 '15 at 13:24
  • $\begingroup$ I was wondering. I misread your explanation as intending to say that you needed closure under subprograms because calling each other as subroutines would not be enough. I wondered whether the use of two different words (subprogram and subroutine) was intended to convey different meanings. I am surprised I cannot find much regarding the halting problem in weak computation models. $\endgroup$ – babou Jul 28 '15 at 14:17
  • $\begingroup$ I had a doubt. You said PDA always halts on reaching the end of the input. Although I know that language recognised by any PDA is decidable. But a PDA may go on infinitely pushing something to the stack , if I am not wrong ? $\endgroup$ – sashas Oct 15 '15 at 13:25
  • $\begingroup$ Looping forever is a key criteria. There are some programming languages, for example, that have no way of constructing an infinite loop. Obviously halting is decidable (it's always true!) The diagonalization argument doesn't apply, because it relies on a program being able to go into an infinite loop. $\endgroup$ – PyRulez Oct 16 '15 at 1:46

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.