A Simple Explanation of the Halting Problem

published

2012-04-12

The halting problem is a problem in computer science that can be stated as follows: Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever. (Wikipedia) Alan Turing proved that there is no program that can solve the halting problem for all possible inputs. Below is a sketch of a proof.

Assume a halting solver h exists that determines whether any program p halts on any input x, where x itself can also be a program. Note that "halt" means that the program terminates, so it is the opposite of "hang". In pseudo-code, we could express h as the following. h(p,x) = return (p halts on input x) Then we can define the following tricky program e. e(p) = if h(p,p) is False then return False else HANG And we can pass the program e as input to e. e(e) = if h(e,e) is False then return False else HANG Now there are only two cases:

1. e halts on e: then h(e,e)=True, which would make e(e) hang - contradiction

2. e does not halt on e: then h(e,e)=False, which would make e(e) halt - contradiction

So we have arrived at a contradiction and our only assumption was that a halting solver exists, so we can conclude that a halting solver cannot exist.

Here is the main idea. This tricky function e calls the halting solver and asks it: "If I were to run myself with myself as input, then what would I do? Whatever you tell me I'll do, I'll just do the opposite." It's really just like the argument that you can't predict someones future actions because they could just ask for the prediction and contradict it. But in a deterministic world, you could predict someone's actions as long as you didn't tell them what the prediction was. Analogously, it may be possible to solve the halting problem for all practically useful inputs. So Turing's theorem alone need not discourage us from seeking reasonably comprehensive code validators.