Today philosophers and mathematicians argue whether Kurt's theorem is of primary importance to mathematics and logic or whether it's overblown. Logicians and philosophers tend to say what Kurt did was as important to the mathematician as Einstein's theory of relativity or Heisenberg's uncertainly principle is to a physicist. But then some advanced mathematicians have said they proceed through their careers with scarce an glance at Kurt's work, thank you. As one mathematics professor recently put it, Kurt warned mathematicians to stay away from certain areas - but those are areas most hard-nosed mathematicians wouldn't go to anyway.

Now it's pretty tough for the average reader to access the merits of these discussions. Kurt's paper is pretty hairy. Filled with symbols, theorems, mapping, and definitions (46 of them!), it's kind of ridiculous to expect Joe Blow to set aside the remote on Super Bowl Sunday while Janet Jackson is one the screen and peruse the little Dover paperback, On Formally Undecidable Propositions of Principia Mathematica and Related Systems. We also have a natural and legitimate skepticism when you hear there is a - quote - "proof" - unquote - that relates to the Secrets of the Universe, but, sorry, it's too complex to explain.

Fortunately coming up with unsolvable problems became kind of the thing to do in the early to mid-part of the Twentieth Century. Just five years after Kurt published his paper, another of the Twentieth Century's mathematical titans (and oft-cited as the founder of computer science), Alan Turing, came up with a nice little proof for the non-provable. Now known as "The Halting Problem", you actually can set down the remote on Super Bowl sunday and read what Alan has to say. Better yet, you can understand it and not miss a second of Janet.

But up front (no pun intended) the reader should be warned. Even when the proof is explained clearly and concisely, many readers have a bit of a "Say what?" reaction. That's due to two things. First, the problem, like many of the more interesting theorems, is an indirect proof. You've probably seen those in school - they're the ones that start off with "Assume that X is true ...". This causes problems for kids trying to prove theorems since they think you can assume what you want is true and then prove it is. Sad to say, this isn't permitted in math.

Instead what you do in an indirect proof (also called reductio ad absurdum) is you assume the opposite of what you want to prove. Then you work backwards until you come up with a conclusion that is nonsense. If you do that, we're told, then your first assumption - the opposite of what you wanted to prove - is wrong. So what you wanted to prove in the first place is correct.

Actually you shouldn't feel too bad if you feel that way. And indeed some mathematicians - called "intuitionists" - don't like using indirect proofs. This is, they don't believe that just because you can prove something isn't true, then you can assume the opposite is. At the same time, strict intuitionists are a minority in the mathematical community, and virtually all mathematicians accept (and use) indirect proofs.

Secondly, Alan's proof - and Kurt's - contain a circular feature. This is not the same as a circular argument (which isn't allowed). Instead it's called self-reference and is where the function uses itself as input. Self-reference is a common feature when proving what's non-provable. Although not - as the rabbi in Fiddler on the Roof said - expressly forbidden, it can leave nagging doubts in your mind. It's like when you say "I am lying" and ask someone if you were telling the truth. For the present, though, this is a bit deep of a topic to go into right now.

In any case, unlike Kurt's proof, Alan's is actually quite simple. The main thing is to take it one step at a time and not get ahead of yourself.

Alan, as many people know, was concerned with computers (he helped break the secret German codes during World War II). So he framed the problem in computer terms. Is it possible, he asked, for a computer to tell us automatically whether 1) a solution exits or 2) if there is no solution?

Rather than use Alan's original approach, we'll defer to modern programming style. So if we have a problem, we'll program it into our computer. If the computer can solve the problem, it stops and spits out the answer. If not, it keeps trying. So if there's no answer (which can also arise from nonsense input) the program runs forever.

Now we can just run the program and see if we get an answer. But how do we know if it can't solve the problem or just is taking a long time? Well, what we'll do is write another program to tell us if our program will work. For now we won't worry about the exact details on how to write such program, and for reasons which will be obvious, we'll call this new program HALT.

What HALT does is to take the first program and its input and first screens its performance. It will say "YES" if our program will work and give us an answer. That is, it can tell if our program will ultimately halt. We could then, if we wish, have the computer then run the program automatically. But HALT will also tell us "NO" if our program will crank on forever without an answer. But remember, HALT itself does not crank on forever. It tells us if our program will.

The best way to understand what we're doing is to use phoney computer language (called pseudo-code by the cognoscenti). In pseudo-code this is what HALT looks like:

In other words, plug any computer program and its input into HALT. We'll be told the answer is either there and if so, we can run the program and get the answer. Or we're immediately told there is no answer and we know not to bother. You could even write a program with HALT as a subroutine where it will or will not run the program automatically or flag it as unsolvable. So clearly HALT then is the ultimate computer program.

The question: Can HALT exist?

To answer that we have to show that no program will confuse HALT. If there is one, then our assumption - that a program like HALT can be written - is false.

Surprisingly, such a program is pretty easy to write. We'll call it "WHOPPER" since it whops HALT. It also uses, we should note, HALT as a subroutine.

At this point it's helpful to state succinctly what WHOPPER does. It will halt, if the input program does not halt. It does halt if the program does not halt. So at this point you might start thinking something is up.

Now let's put WHOPPER into WHOPPER. Can we do this? Sure. WHOPPER is a computer program that accepts any computer program as input. There's no reason you can't feed WHOPPER's code into itself. So now we have

So what happens? There are only two possible outcomes. Let's consider these separately.

The first possibility is we run WHOPPER( WHOPPER ) and it halts. Well, we know then that "control" of the program was directed to the second line.

But wait a minute! If WHOPPER halts - and is controlled by the second line - that means HALT identified WHOPPER as a program that did not halt! So if WHOPPER( WHOPPER ) does halts, that means WHOPPER( WHOPPER ) does not halt!

And if WHOPPER does not halt? Then the control was directed to the first line. But again there's the problem. Control goes there only if HALT says WHOPPER does halt! So if WHOPPER( WHOPPER ) does not halt, that means WHOPPER( WHOPPER ) does halt!

In other words, WHOPPER( WHOPPER ) halts if and only if (as the philosophers say) WHOPPER( WHOPPER ) does not halt. Ladies and gentlemen, we have a contradiction.

Why the contradiction? Well, since we're using an indirect proof, it means we're using a false assumption somewhere. And our assumption? That we would write the perfect program, HALT.

So in the end we can't write HALT. No computer will be made to automatically solve every problem.

What? Something still bothering you. Something still nagging at the back of your mind?

Godel's theorem created an equation which was equivalent to saying "I can't be proven" which was true and so couldn't be proven. But, you ask, what's the point of such an equation? What does it do other than just say - however correctly - that it can't be proven? How does that affect anything else?

Here's where the division between hard-nosed mathematicians and logicians comes in. Some mathematicians say that although Godel's theorem is correct, it changes mathematics surprisingly little. If selecting a career in mathematical research, you can quite easily coast along without scarce a glance what Kurt did, thank you.

And Alan's proof? You want to know what good is there in writing a program when all it does is flummox another program? What would that program do for us otherwise?

Or to put it another way. We started off saying we were interested in solving a problem and to write a computer program that would solve any problem. But just what problem is WHOPPER solving? All it does is confuse HALT? Is this a problem in the normal sense of the word? Have we somehow changed the rules in mid-game?

Now experts might dismiss these concerns as being the philosophical ramblings of the layman who wastes is time posting cartoons on the internet . But Stanislaw Ulam, the Polish mathematician who worked with Edward Teller on the H-bomb, said he always had the impression that Kurt worried that he might not have done anything as great as many people thought. Maybe all he had done was come up with a new (although crafty and clever) paradox.

But how useful a specific case may be isn't the point. But what Kurt and Alan (and the Princeton professor Alonzo Chuch) did was show us using consistent formalized mathematics with rules that we accept for doing all we want to do, you can create legitimate expressions and formulas that are true but can't be proven within the system.

That's the point.

References

Alan Turing: The Enigma, Andrew Hodges, Simon and Schuster (1984). Alan's volumous biography.

"Alan Turing", The MacTudor History of Mathematics Archive, http://www-history.mcs.st-andrews.ac.uk/Biographies/Turing.html. Probably one of the best sources for biographies of mathematicians and logicians on the web. Huge number of entries from ancient to modern times. Most entries have a lot of detail about the people. And thank heavens it's a non-commerical website. No animation, no ads, and easily navigated. The home page is: http://www-history.mcs.st-andrews.ac.uk/

"On Computable Numbers with Applications to the Entscheidung-Problem", Proceedings of the London Mathematical. Society, Vol. 42, 230-265 (1936). Alan's paper doesn't use modern programming and shows that a "Turing Machine" can be given a problem it can't solve. Still, t's worth the effort to understand Alan's original argument and methodology.

Online at http://www.turingarchive.org/browse.php/B/12 but not in a terribly convenient form.

"Computing Machinery and Intelligence", Mind Volume 59, pp. 433-460. Alan's original paper on the imitation game ("The Turing Test"). Easy to read and understand. An online vesion is at http://www.loebner.net/Prizef/TuringArticle.html

"Alan Turing", http://plato.stanford.edu/entries/turing/ The Stanford History of Philosophy - Online, free, no registration, but not (thank goodness) completely open access. The articles, though, are of variable quality, but at least the articles are written by people who know the subject. This article is by Alan's biographer, Andrew Hodges

"Official Alan Turing Website", http://www.turing.org.uk/turing/index.html The web site is also by Andrew. Quite a lot of information. One gripe: flickering, if minor, animation