[Solved]: What is the amount of programs for which we can solve the halting problem?

Problem Detail: 

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.

Asked By : Programmer2134

Answered By : Ben

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63522

3.2K people like this

 Download Related Notes/Documents