1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ " This implies that there is at least one program for which we cannot decide whether it halts or not" -- That's not even wrong, and that's your fundamental misunderstanding. If you resolve it, the question goes away. In short, thinking about the halting problem without infinity resp. looking at all problems does not make any sense. See e.g. here. I think we also had questions on large classes with decidable halting problems, but I can't find it at this moment. $\endgroup$ – Raphael Sep 16 '16 at 6:49
  • $\begingroup$ Also, note that there are infinite sets of TMs for which the halting problem is (collectively!) decidable, and the set of all TMs is, of course, infinite, so the ratio you are looking for would not even exist if your intuition about the halting problem was accurate. $\endgroup$ – Raphael Sep 16 '16 at 6:54
  • $\begingroup$ I don't think that statement you quoted is "not even wrong". It may be a wrong conclusion, but it seems to be a clearly defined statement. it means: there is a subset of the set of programs, that has only one program as its element, and the subset of programs that halt, of that subset, is undecidable. $\endgroup$ – user56834 Sep 16 '16 at 7:07
  • 3
    $\begingroup$ For every fixed program the halting problem is decidable. $\endgroup$ – adrianN Sep 16 '16 at 8:04
  • 1
    $\begingroup$ @Pseudonym: that's not relevant. Chaitin's constant is about the proportion of programs that halt. This question is about "the proportion of programs whose halting can be decided", whatever that means. $\endgroup$ – Andrej Bauer Sep 16 '16 at 14:49
4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My textbook defines that a set is decidable iff there is a decision procedure for it. So I don't really understand why you're introducing the complication of there being a decision procedure but it not being computable. If a decision procedure is not "computable", then I would say the procedure simply doesn't exist. Perhaps the terminology in my textbook is different from what is employed elsewhere. In any case, are there rough estimates of Sp? even if it is not well defined, which would seem to me personally to be very unlikely, there could be some estimate of a value around which Sp hovers? $\endgroup$ – user56834 Sep 16 '16 at 13:01
  • 1
    $\begingroup$ I elaborate the answer. Please read carefully and try to understand why what you are saying is a moving target. $\endgroup$ – Andrej Bauer Sep 16 '16 at 13:17
  • $\begingroup$ My question is about attempt 3. I still don't quite understand what attempt 1 has to do with this, but regarding attempt 2: if we have a decision procedure D1 for program P1 and a (possibly different) D2 for P2, then we can create D which, if it is fed P1, applies D1, and if it is fed D2, applies P2. This is why I assumed that whether every program is halting-decidable by a different decision procedure or by the same (assuming they are halting-decidable) is irrelevant, since a new universal decision procedure can be constructed. In any case, It is the value Sp that you defined that I'd like. $\endgroup$ – user56834 Sep 17 '16 at 16:13
  • 1
    $\begingroup$ What you say about P1 and P2 is ok, but what if you have to consider infinitely many problems P1, P2, P3, ...? Then, how will you compose D1, D2, D3, ... into a single procedure? $\endgroup$ – Andrej Bauer Sep 17 '16 at 17:42
  • 1
    $\begingroup$ Attempt 1 and Attempt 2 are relevant because the way you phrased your question it reads as a question about Attempt 1 or Attempt 2. Your formulation does not speak about Attempt 3. Your teminology is messed up. And I think it's not just terminology, you actually do not see the difference between Attempt 2 and Attempt 3. That's what everyone here is trying to teach you. So, again, please read carefully what I and all the other people are saying. $\endgroup$ – Andrej Bauer Sep 17 '16 at 17:44

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.