2
$\begingroup$

The undecidability of the halting problem implies that no Turing machine can determine whether an arbitrary Turing machine passed to it will halt or not on a given input. However, we can devise algorithms that are right some of the time. In the simplest case, an algorithm that always returns "halt" will be correct for any Turing machine that halts. This is, however, not very useful. Can we do better?

What I am curious about is whether there are any results that pin down how good a partial solution to the halting problem can be before we run into trouble. Is there a Turing machine that solves the halting problem for almost all inputs? If not, is there a weaker condition we can ask for that can in fact be met?

More generally, let a "weak halting problem" be a problem obtained by replacing the universal quantification in the halting problem (the requirement that a Turing machine determine whether its input halts for all possible inputs) with some weaker notion of quantification. Which such weak halting problems are solvable?

$\endgroup$
4
  • 2
    $\begingroup$ This depends on exactly how we phrase the question. Compare e.g. Hamkins/Miasnikov and Rybalov. $\endgroup$ Nov 15, 2023 at 20:59
  • 1
    $\begingroup$ What would "almost all" mean in this context. Finitely many exceptions? Asymptomatically no exceptions e,g. all integers contain the digit 9? $\endgroup$
    – badjohn
    Nov 15, 2023 at 21:29
  • $\begingroup$ Incidentally, the set of (integer representations of) Turing machines which halt for all inputs is not even recursively enumerable. (Informally, there is no program which can print a stream of programs which halt for all inputs, without missing one.) $\endgroup$ Nov 15, 2023 at 22:55
  • $\begingroup$ There's a substantial literature on what practical problems can be solved in programming languages where every program is guaranteed to halt; such languages put a lot of effort into proving that the given program must halt, and a number of useful techniques for this are known. For an archive of the literature, see github.com/mietek/total-fp . $\endgroup$
    – MJD
    Nov 16, 2023 at 0:39

1 Answer 1

1
$\begingroup$

It is probably impossible to know for sure, because if you can define a property of Turing machines that gives you information about the halting problem then that property is probably itself incomputable.

For example, consider the Busy beaver function. It's a function that, given a real number $n$, outputs the maximum number of steps an $n$-state Turing machine can run for before halting, if it halts at all. This function is incomputable, because otherwise you could create an Oracle machine that takes in an $n$-state Turing machine, runs it for $BB(n)$ steps, and if it hasn't halted can conclude that it will never halt.

With that said, this gives us some information about one way a "weak halting Oracle" can work - if you take some of the theoretical lower bounds for the Busy beaver function, you could instead use those to determine how long to run the input machine for, and that would correctly identify some reasonable number of halting machines. That lower bound grows insanely huge quite quickly, though, so if you were to actually try building this Oracle you would need to run it for multiple lifetimes of the universe even for small values of $n$.

$\endgroup$

You must log in to answer this question.

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