A Simple Explanation of the Halting Problem
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:
- e halts on e: then h(e,e)=True, which would make e(e) hang – contradiction
- 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.
Read more from the Logic category. If you would like to leave a comment, click here: Comment. or stay up to date with this post via RSS from your site.
Leave a Comment
If you would like to make a comment, please fill out the form below.