What is the actual scope of the Halting Problem impossibility result?

Question

Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function D(X) = {if H(D,X) then loop; else Halt;} can be constructed, with D(D) leading to a contradiction => hence H can’t exist.

However, this proof relies on the fact that H decides Halting for any (TM,Input) pair as input - and so in particular, it can be given (D,D) to decide. But what if we suppose that H decides Halting for everything except D(D). Does the proof fall apart?

It seems that from “H can’t decide D(D)” we jump to the conclusion that “No TM exists that solves the Halting problem for any TM”. While that conclusion is technically valid, maybe there’s a TM that decides Halting for ‘virtually all’ Turing Machines, except a tiny subset - which includes D(D), or possibly D(any input), or even some slightly larger set. The above proof doesn’t preclude that.

Is there a more quantitative statement of the Halting Problem impossibility result - something that gives some measure of how many TMs (or a description/characterization of which ones), out of the set of all possible TMs, no single function can decide whether they halt or not?

To put it another way, maybe it's possible to construct a Halts() function that will be correct on 99.99999…% of its inputs? Or to be more precise, given a Halts() function candidate, we can state something quantitatively, along the lines of : Correctness = $ \lim \limits_{n \to \infty} \sum_{1}^{n} \frac {IsCorrect(Halts(n))}{n}$ (where the sum is over the indices of TMs in some fixed enumeration, and IsCorrect returns 1 if Halts(n) is correct). Now we can ask 1) Are there Halts() functions for which this limit exists? 2) Out of those, which ones maximize this limit?

The import of this is that if there's a Halts() function with a correctness close enough to 1, then the Halting undecidability theorem can be viewed as having little practical value and as being more of a curiosity applicable to a tiny subset of degenerate cases. Even though Rice's theorem shows a wide variety of questions that are undecidable because they can be reduced to the Halting problem, for each of those questions individually, the 'Correctness' limit above might still be close to 1, and so again, we'd be able to find algorithms that decide them for all practical purposes (save a few odd cases).

Note: This question is similar to what's asked in "Attempt #3" of this answer, but it doesn't look like that was ever addressed further (i.e. whether there's any research or literature that investigates such a limit).

Answer 1

Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and:

1. If $H$ terminates and outputs "yes" then $M(x)$ halts.
2. If $H$ terminates and outputs "no" then $M(x)$ does not halt.

In particular, $H$ is allowed to run forever and not give an answer.

Given two partial Halting oracles $H_1$ and $H_2$ we may combine their powers by running them in parallel, and if either one ever halts and gives an answer, we output that answer. Let us write $H_1 \oplus H_2$ for such a combined partial Halting oracle.

Consider the partial Halting oracle $L$ which works as follows on input $(M,x)$: it simulates the working of $M$ on input $x$, and if the simulation ever terminates, it terminates with output "yes". Then $L$ correctly predicts all cases that halt, and no others.

Given any partial Halting oracle $H$, we can always combine it with $L$ to get a partial Halting oracle $H \oplus L$ that correctly predicts all the halting cases. The only question then is, how good a predictor of non-halting can be implemented.

Define the non-halting set $$\overline{K} = \{(M,x) \mid \text{$M(x)$ does not halt}\}$$ and for any partial Hlating oracle the set $$S_H = \{(M,x) \mid H(M,x) = \text{"no"}\}.$$ We then have $S_H \subset \overline{K}$, $S_H$ is computably enumerable, and $\overline{K}$ is productive. Computability theory teaches us that $\overline{K} \setminus S_H$ is infinite, i.e., every partial Halting oracle fails infinitely often.

You may try to measure the ratio of $S_H$ to $\overline{K}$ in some fashion, such as the measure you suggest in the question. However, the problem with all such measures is that they heavily rely on how machines are coded. By passing to a different coding we can maipulate the measure to be whatever number we like, so that is not very helpful. For instance, to get a 99% success rate, use the following coding: a number of the form $100 n$ encodes the machine encoded by $n$ in some standard encoding, while a number of the form $100 n + r$ with $0 < r < 100$ encodes a machine that obviously never halts (always the same machine).