Undecidable problems are yes/no questions which (for some or all inputs) are impossible to answer. A famous example is the "halting problem."
Even for undecidable problems, it may be possible to compute the answer for some of the inputs; however, you can't comute the answer for all inputs.
This page will show that the halting problem is easy to understand, and also that it is undecidable.
We want to write a computer program called "HALT" that will tell us if a second program will "halt." This would be useful for software programmers, because they could tell whether a certain program will have an infinite loop or not. The halting problem is the question of whether it is possible to write a program HALT which computes a correct answer for all programs. The answer is "no," and so this problem is undecidable.
The halting function is a program, written in whatever language you like (it does not matter), which accepts two inputs and returns one yes/no answer. We represent an invocation of the halting program using the notation
| HALT(x,y) |
This notation means that HALT is a function accepting two inputs, x and y, in that order.
The first input (x) is another arbitrary program in the same language. This can be any program at all. Since x is a program, it is a function just as HALT is, and an invocation of it can be written:
| x(z) |
The second input (y) to the halting program is the input for the first input of the halting program. It would be valid to invoke x and give it the input y as follows:
| x(y) |
We ask the question, are there any infinite loop bugs in x? In particular, if we ask a computer for the value of x(y), will it enter an infinite loop or terminate with an answer? (These are the only two possibilities.) This question is specifically answered by the halting program. It returns YES if and only if x(y) terminates (halts) with an answer. We express the function HALT as follows:
| HALT(x,y) = | { | YES | if x(y) terminates | |
| NO | if x(y) has an infinite loop |
Create another function I(z) which returns true if HALT(z,z) returns NO, and which loops forever if HALT(z,z) returns YES. (Note the program z is being passed as input to itself.)
| I(z) = | { | infinite loop | if HALT(z,z) returns YES | |
| YES | if HALT(z,z) returns NO |
Now, what is the value of the invocation
| HALT(I,I) |
If I(I) terminates, then HALT(I,I) must return YES (by definition of HALT). However, if HALT(I,I) returns YES, then I(I) enters an infinite loop and thus never terminates. Thus HALT(I,I) must return NO. This is a contradiction.
Suppose instead I(I) does not terminate. Then HALT(I,I) must return NO (by definition of HALT). However, if HALT(I,I) returns NO, then I(I) immediately returns YES, thus terminating immediately. Thus HALT(I,I) must return YES. This is a contradiction.
There are no other possibilities. Therefore, it is impossible to create such a function HALT that a computer can compute. Thus, the halting problem is undecidable.
(Note: The are some formalities required to make this a formal proof that I have omitted for the sake of simplicity. Trust me, it's true.)
Contact the malingerer@undecidable.com last updated 2015-08-30