This blog is highly personal, makes no attempt at being politically correct, will occasionaly offend your sensibility, and certainly does not represent the opinions of the people I work with or for.
The halting problem
avatar

I had a discussion with someone this afternoon about among other things, the halting problem and transfinite numbers. I wrote two texts in the train coming back home. This entry is about the halting problem (for human beings), the following one will be about transfinite numbers.

The halting problem.

The fact that some programs loop for ever on some input, is a problem. Wouldn't it be great if compilers could raise the following error ? "This program doesn't stop on some inputs".

More generally, the "halting problem" is the problem of deciding mecanically (in other words, by program) whether a program P will halt or not on some data d. I do not claim that this problem cannot be partially solved. In fact compilers already recognize some cases, but solving the problem would be that a program *for all pairs* (P,d), where P is a program and d some data, decides whether the run P(d), will stop or not.

We will assume that all programs always accept all inputs. Meaning that given any program x and any data y, then the run x(y) can be performed. Maybe the data y was meaningless for the program x, as in trying to read a Word file with a mp3 player, and in that case the result of the run would be meaningless, but at least the program will run.

I am going to demonstrate that the halting problem cannot be solved. In other words, I am going to establish the theoretical impossibility of the existence of a program called Halt, which would have the following properties.
    - Halt always stops with an answer "yes"or "no".
    - Given a program P, and some data d, then Halt(P,d) replies
            "yes" if the run P(d) stops and replies
            "no" if the run P(d) doesn't stop.

Let us assume that such a program exists. Let us now define a program called K defined as follows

K(u) := while(Halt(u,u)="yes"){}

K is a program, isn't it, so it is legitimate to consider the following: K(K). Regardless to what does "K(K)" mean, we have the following.

K(K) stops
	        iff Halt(K,K)="no" (by definition of K)
	        iff K(K) doesn't stop (by definition of Halt)

...as we can see an unavoidable contradiction rises from the hypothesis that Halt exists.

[ add a comment ]

Archives