Halting Problem

Turing proved that there was no foolproof way, i.e. program, to test whether another program applied to some input would halt and produce an answer.

To begin, notice that it is possible to produce a never-ending list of all the programs, M₀, M₁, . . . , M_i, . . . by ordering them first by length, then by alphabetical priority. Thereafter, we can designate a program by its number on the list.

Theorem 1. There is no program, call it Always_Halts(i), that could test whether M_i halted for every possible input.

Proof: If the program Always_Halts existed we could use it to produce a never-ending list of all the machines, H₀, H₁, . . . that always halted by going down the list of programs and removing ones Always_Halts rejected. Now imagine the program B (for Barber) which, given input i, applies H_i to i and outputs the answer plus 1. It always halts since H_i always halts. However, B cannot be on the list because, if it were on the list at index j, H_j(j) == H_j(j)+1, which is impossible. Thus, we must conclude that Always_Halts cannot exist.

QED

Theorem2 : There cannot be a program, Will_It_Halt(i, j) that answers “yes” if M_i applied to j will halt, “no” otherwise.

Proof: Assume Will_It_Halt exists. We could use Will_It_Halt to implement Always_Halts as follows: Consider the program M_n(i) that asks Will_It_Halt(i, j) for j = 0, 1, . . . returning 0 if Will_It_Halt(i, j) ever says “no,” but runs forever otherwise. Now implement Always_Halts(k), by saying “yes” if Will_It_Halt(n, k) says “no” and vice-versa. From this apparently successful implementation of the nonexistent Always_Halts we must conclude Will_It_Halt can’t exist.

QED

Everyone thinks this proof is a trick until they read it for a few days.

This just in: Even quantum computers have this problem.

You may be thinking that you don’t care if bizarre programs like Barber are impossible, but subsequent mathematical investigations, especially by an IBM mathematician Gregory Chaitin, show that many other programs cause such problems.

Chaitin, has recently proven even more convincingly that there are infinitely more true theorems that can’t be proved via an axiomatic system than theorems that can be proved. He goes on to make the heretical—for mathematicians—suggestion that mathematics should become, like the rest of science, an endeavor where experimental evidence is good enough to prove something. His argument is buttressed by the fact that computers can be employed to generate voluminous amounts of experimental evidence. I wish my high school geometry teacher could hear this.