What is the amount of programs for which we can solve the halting problem?

Question

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the halting problem is undecidable, it could still be that there is a program that can decide for every program except itself whether it halts or not.

So I am wondering, for what percentage of programs can we solve the halting problem? That is, if we assign a Gödel number G to every program. What is the value of the limit with respect to G to infinity of:

${s}/n$

where s = the number of programs with Gödel number 1 to G, for which we can decide whether it halts or not.

and n = the number of programs with Gödel number 1 to G, for which we cannot decide whether it halts or not.

I am not looking for a specific answer like 75%. I am looking for an answer like: less than 0.01 % or more than 9.99%, or anything really that gives a hint at an answer.

Answer 1

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not.

The undeicidability of the halting problem actually doesn't imply this. It means that there is no single algorithm that can tell whether any program halts. It does not mean that there is any single program for which no algorithm can correctly say whether or not it halts.

Note that a program either halts or doesn't on each particular input. The general halting problem is a function from (program, input) pairs to booleans. You're talking about the halting problem in terms of "this program halts, that one doesn't" without talking about inputs. So either you're thinking of one of the formalisms of the halting problem where you just assume you run all the programs with an empty input (or zero if the inputs are numbers, or whatever; it's all basically the same), or you're thinking of "for a given program, does it halt for all inputs" style versions of the halting problem. It doesn't matter though, for this discussion.

Whatever definition of "program halts" you're using, a program either halts or it doesn't. HALT(P) is True or False for all P. You claim that there must therefore be some program P for which no other program correctly computes HALT(P), otherwise we could union up all the pointwise decision procedures for each individual P into one that works for all P.

In fact though, I can concretely give you a set of decision procedures such that for all P, one of them gives the correct answer to HALT(P):

1. regardless of input, return True
2. regardless of input, return False

In the "just delegate to a subprogram that works for this particular input" strategy, you're actually doing all the real work in the part that decides how to delegate. If you could actually do such a delegation (such as by enumerating the pointwise decision procedures for the halting problem alongside the programs that they work on), you would already have decided the halting problem by the time the delegation part of the program is finished; the answer is just encoded in another program that you have to run, instead of a more direct encoding of boolean values.

To try to get an intuition for why this sort of delegation can't work, think about how you could actually attempt to implement it in (say) a Turing Machine.

If you have a unique pointwise solver for each program, then you simply can't hardwire them all into the Turing Machine, because there are an infinite number of them and you only have a finite number of states to implement them.

If you imagine that there are a finite number of sub-solvers to dispatch to (which is definitely possible, since "return True" and "return False" are a sufficient set), then you're assuming that your Turing Machine can analyse each input program to figure out which sub-solver would work on it. But how would you implement that analysis? It essentially is an obfuscated version of the halting problem. For any set of partial halting-problem solvers, you should be able to take any standard "halting problem is undecidable" proof and replace the part where the assumed solver outputs true or false with having it output an indication of which partial solver you should run; it'll be easy to use that to construct the same sort of contradictions. (i.e. "Which partial solver does the delegator indicate would correctly decide whether the delegator halts?")

Your argument hasn't shown that there must be a P for which there is no program that computes HALT(P) correctly. It actually shows that there is no algorithm for carrying out the delegation strategy you outlined.

Neither can you "enumerate a list of such decision procedures for each individual program" as mentioned in one of the comments. Well, technically you can, since my list of 2 programs above was such an enumeration, but you can't enumerate a list of decision procedures paired with the programs that they work on.

Answer 2

If we read the question as written then the answer is 100%. Let us be careful about what is being asked.

Attempt 1

Consider the set of numbers $n$ such that the $n$-th program either halts or it does not. If you believe in classical logic then every number is in this set, because "the $n$-th program either halts or it does not" is an instance of the Law of Excluded middle. So the answer is 100%.

Attempt 2

Sometimes people try to fix Attempt 1 by differentiating between "program $n$ halts or it does not" and "we have a decision procedure for $n$" (as witnessed by the comment "For every fixed program the halting problem is decidable." by adrianN above). That is, they think that it makes sense to have many decision procedures, one for each number. This leads to the following (failed) attempt:

Consdier the set of numbers $n$ such that there is a decision procedure for the halting of the $n$-th program. Once again every number is in this set:

1. If the $n$-th program halts then the decision procedure is print "it halts".
2. If the $n$-th program does not halt then te decision procedure is print "it does not halt".

However, and this is quite important:

• we are here not talking about a single (posssibly non-computable) decision procedure,
• we are talking about many decision procedures, one for each number (which is weird, which is why this is a failed attempt)
• if we try to combine the decision procedures together somehow, we have a problem: even though for each particular $n$ there is a decision procedure $D_n$, the function $n \mapsto D_n$ is not computable

Attempt 3

The lesson learned from Attempt 2 is that we need one decision procedure that handles all numbers. But there is no such decision procedure because it would be a Halting oracle. We can still ask how well can we do with a single procedure?

Say that a procedure $P$ is a partial Halting oracle if, for every $n$,

• $P(n)$ is undefined, or
• $P(n) = 1$ and the $n$-th machine halts, or
• $P(n) = 0$ and the $n$-th machine does not halt.

Define the success rate $s_P$ of such a decision procedure $P$ to be $$s_P = \lim_{n \to \infty} \frac{\big|\{i \leq n \mid \text{$P(i)$ defined}\}\big|}{n}$$ Now we can ask whehter $s_P$ is well-defined (does the limit exist)? If sohow big can $s_P$ be?

Summary: The way you asked your question looks like you are going for Attempt 1 or Attempt 2, but it is not really clear. The problem is that you speak of "a solvable program". That does not make any sense. Every single program "is solvable" because it either halts or it does not (attempt 1, maybe attempt 2). You need to phrase the question carefully.

Answer 3

Andrej made a good point in that phrasing the question correctly is difficult and important. Your comment indicated that you wanted the answer to the only "interesting" way of formulating the question: "how well" can a program approximate the halting problem? I co-authored a paper on exactly this, and some related questions. It was published at ICALP 2015, then the long version was published in LMCS. A summary is below.

First, the notion of a "proportion of programs" is heavily dependent on how you enumerate all possible programs. Common programming languages are "sparse": if you generate a random string of bytes, it likely won't be a valid C program, for example. So most programs are "trivial", and once you choose the convention (e.g. nonsensical programs halt), then you can approximate the halting problem by saying "all programs halt", and be right almost 100% of the time. Of course, that's completely uninteresting. The right way to avoid this is to require the enumeration $A_1, A_2, ...$ to be optimal: for any other enumeration of programs $B_1, B_2, ...$ there exists a constant $K$ such that every program $B_i$ is equivalent to some program $A_j$ with $j<i+K$. These "optimal programming languages" aren't hard to build, and they're important building blocks in the theory around Kolmogorov complexity.

OK, so now that the subtlety about programming language optimality is out of the way, are we done with the preliminaries? Not really: we also have to define what it mean for a decision procedure to approximate the halting problem. Is it allowed to never return for some outputs, like in Andrej's answer? Is it allowed to make mistakes? Let $P$ be the decision procedure: $P(i)$ tries to guess whether $A_i$ halts. Let's define its success rate at step $n$:

$$ s_P(n)=\frac{\left\{i<n \mid P(i) \text{ halts and is correct} \right\}}{n} $$

Further, are we interested in the "guaranteed" rate of success for sufficiently large $N$? Or are we interested in "how muchthe $\liminf$ or the $\limsup$ of $s_P(n)$? (See here for definitions.)

The outcome changes depending on the answers to the previous questions. But here is the tl;dr, with pointers to the theorems in the long version of our paper.

• For any procedure P, there will be an $\epsilon>0$ and a $N$ such that for all $n>N$, $s_P(n)<1-\epsilon$. This holds even if you allow $P$ both to never halt sometimes, and to make errors (Theorem 3.1.a.).
• Now, can we make the $\epsilon$ independent of the procedure $P$? Kind of: there exists a $\alpha$ such that for any procedure $P$, $\liminf_n s_P(n)<1-\alpha$. Put another way, the rate of error is going to be above some fixed constant, infinitely many times. Again, this holds even with a $P$ that can both never return or be wrong (Theorem 3.1.b).
• OK, but can we make the $\limsup$ as high as we want? Yes! For every $\epsilon>0$, there exists a procedure $P$ such that $\limsup_n s_P(n)>1-\epsilon$ (Theorem 3.1.c).
  • Except! What if we force the procedure $P$ to be error-free, like in Andrej's answer? Can we still make the $\limsup$ as high as we want? The answer is a shocking it depends on the optimal programming language. This is, by the way, extremely surprising: almost every other result in algorithmic complexity does not depend on the choice of the language (Theorem 3.1.d).

The negative results (the first two bullet points) also hold if $P$ is allowed to be probabilistic in a "naive" sense (Theorem 3.3.), by letting the procedure have access to random bits. You can also formalize the notion of "solving the halting problem probabilistically" in a more complex way, that makes a little more sense in this context, in which case you get slightly (but not very) different results (Theorems 5.1, 5.3 and 5.5).