{"id":303,"date":"2007-02-06T22:05:30","date_gmt":"2007-02-06T22:05:30","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/06\/basics-the-halting-problem\/"},"modified":"2007-02-06T22:05:30","modified_gmt":"2007-02-06T22:05:30","slug":"basics-the-halting-problem","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/06\/basics-the-halting-problem\/","title":{"rendered":"Basics: The Halting Problem"},"content":{"rendered":"

Many people would probably say that things like computability and the halting
\nprogram aren’t basics. But I disagree: many of our basic intuitions about numbers and
\nthe things that we can do with them are actually deeply connected with the limits of
\ncomputation. This connection of intuition with computation is an extremely important
\none, and so I think people should have at least a passing familiarity with it. <\/p>\n

In addition to that, one of the recent trends in crappy arguments from creationists is to try to invoke ideas about computation in misleading ways – but if you’re familiar with what the terms they’re using really mean, you can see right through their
\nsilly arguments. <\/p>\n

And finally, it really isn’t that difficult to understand the basic idea.
\nReally getting it in all of its details is a bit harder, but just the basic idea that there are<\/em> limits to computation, and to get a sense of just how amazingly common uncomputable things are, you don’t need to really understand the depths of it.<\/p>\n

<\/p>\n

It makes sense to start with a bit of history. Before people actually built real
\ncomputers, there was a lot of interest in what could be done by a purely mechanical
\nprocess. In fact, the great
\nproject of mathematics in the early 20th century was the attempt to create a perfect
\ncomplete mathematics<\/a>, which meant a new formalization of math in terms of a logic
\nin which every<\/em> true statement was provably true; every false statement was
\nprovably false; and given any statement, you could follow a completely mechanical
\nprocess to find out whether it was true or false.<\/p>\n

You most commonly hear about how Gödel wrecked that with his incompleteness theorems. But Alan Turing did something that demonstrates the same basic principle: defining the limit<\/em> of what could be done by a purely mechanical computation process. In the end, what Turing showed about computability is really the same concept as what Gödel showed about logic with incompleteness: the limits of
\nmechanical\/axiomatic processes.<\/p>\n

Fundamentally, what Turing did was prove that there are things that cannot be
\ncomputed. He did that two ways: first, by defining an easy to understand problem which
\ncannot be solved by any mechanical device; and second, by showing how common
\nnon-computable things are.<\/p>\n

The first of Turings two proofs is commonly known as the Halting problem<\/em>.
\nThe simplest version of the halting problem is the following. Suppose you have
\na computing machine M, and some program, P which can be run on M. Can you write a program which can by looking at P can determine whether or running P will eventually stop?<\/p>\n

I actually find the more formalized presentation to be clearer. Take a computing
\nmachine, which we’ll call φ. (Don’t ask why φ, it’s just tradition!) Now,
\nsuppose we have a program P<\/em> for φ which computes some function on its
\ninput. We’ll call that function φP<\/sub>. So φP<\/sub>(i) is the
\nresult of running the program P on the input i using the machine φ.<\/p>\n

So the halting problem is really the question: given a machine φ, is there
\na program H where φH<\/sub>(P,i) = YES if and only if φP<\/sub>(i) will halt, and will return “NO” if φP<\/sub>(i) would not<\/em> halt. The program H is called a halting oracle<\/em> – so the question is, is it possible to write a halting oracle?<\/p>\n

The answer is no<\/b>. You can’t write a program like that – no such program can possibly exist. And it’s actually really quite easy to show you why – because if there were<\/em> a halting oracle H, it’s very easy to write a program for which H<\/em> is guaranteed to get the wrong answer.<\/p>\n

Take the halting oracle program H. Write a program T which includes<\/em>
\nH, and which does the following:<\/p>\n