The Halting problem means that there is no algorithm which correctly determines whether an arbitrary program will halt. However, there may be a program which is able to correctly predict whether one program will halt given a certain input. For example, a program that just changes a single cell and then halts is easy to predict. The algorithm simply always outputs "Yes, it will halt." On the other hand, it is impossible to write an algorithm that can predict whether a Universal Turing Machine will halt given an arbitrary input, because that would solve the Halting problem, since Universal Turing machines can simulate any program given any input. In-between these two examples are Turing machines which sometimes halt and sometimes do not depending on the input, and for which an algorithm exists which always correctly says which will occur. For example, if the initial cell is 0, it will halt. If the initial cell is 1, it will not halt.

Is there an algorithm which can determine for all programs whether or not there exists an algorithm which can predict given a certain input whether it will halt? Note: this is not the same as the Halting problem because even if I can tell that the Halting problem cannot be solved for a given program, I still cannot tell which specific inputs are indeterminable. Is there some way to quantify the amount of Turing machines which have this property or don't probabilistically? Obviously since there are infinite Turing machines the choice would be somewhat arbitrary, but I guess I'm looking for something like "x % of programs with n states have an algorithm that predicts if they will halt."

  • $\begingroup$ Or, you could ask what fraction of ("partial"?) Turing machines have a solvable halting problem...? Probably harder to have an algorithm to assess a given Turing machine...? :) $\endgroup$ Commented May 1 at 23:36
  • $\begingroup$ @paul garrett yes, a program that could calculate a general probability would be easier. $\endgroup$ Commented May 6 at 4:56

1 Answer 1


Consider "two-part" programs $P_y$ parametrized by bit-strings $y$. Given input $x$, $P_y$ first simulates a universal Turing machine on the input $y$. If that halts, it then simulates a universal Turing machine on input $x$. Thus if $y$ happens to be an input for which the universal Turing machine runs forever, then $P_y$ will never halt, and your hypothetical algorithm should say "yes, there is an algorithm" (namely always say "it won't halt"). But if $y$ happens to be an input for which the universal Turing machine halts, then your hypothetical algorithm should say "no". Your hypothetical algorithm would thus have to solve the Halting Problem, and that is impossible.

  • $\begingroup$ What do you mean by "simulates a universal Turing machine on input" $z$? Is $z$ treated as an index of a Turing machine being simulated, the input to that Turing machine, or both? $\endgroup$
    – blargoner
    Commented May 2 at 1:58
  • $\begingroup$ $z$ is the input to the Turing machine being simulated. $\endgroup$ Commented May 2 at 5:39
  • $\begingroup$ Does this also imply that there is no probabilistic means for determining how likely it is the halting problem can be solved for a random Turing machine? $\endgroup$ Commented May 6 at 4:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .