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 on 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 an indirect proof is, well, indirect. 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. For instance, self-references make perfectly good sense such as "This sentence has five words." Pefectly true. But then there's the famous "This statement is not true." If that statement is true, it is not true. And if it is not true, then it must be true. So the statement is both true and false. Now there are various ways around this. And you can argue you have just proven - via an indirect proof - that a sentence that refutes its own truth is not actually a statement at all. For the present, though, this type of stuff 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 exists 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 phony 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. HALT will tell us if anyprogram halts - that is, if the program has an answer. If it does, 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. Is this really proving anything? Or perhaps you ask just what is the point of such an equation? What does it do other than just say - even if 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. As we said, 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. One professor of mathematics at a major university said that what Kurt did was prove that if you define the word "number" carefully enough, then you will be able to prove there are equations about numbers that can't be proven.

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. Again we ask 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? If so, then we can argue Alan did nothing more than what Jules Richard did when he developed Richard's paradox.

Now experts might dismiss these questions 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, Kurt worried, all he really had done was to come up with a new (although crafty and clever) paradox.

So is that what Alan did? Did he change his rules - that is alter the definition of what we mean by solving a problem in mid-proof? Do we, then, have nothing more than a parlor game type paradox? Are we really solving a problem?

Well, the computer can cite what Tonto said when he and the Lone Ranger were surrounded by a band of Indians. "Well, Tonto," the Lone Ranger said. "It looks like we're finished." "So what do you me we, kimosabe?" Tonto asked.

We may have changed the game in mid-proof but the computer did not. That is a computer doesn't necessarily look on the concept of solving a problem like a person does. True you can make a program stop in many ways. For instance, pick a random number and then have the computer start generating other numbers. Then have the computer stop when it selects a number greater than the one first picked. So the program has stopped. But a person can say this "problem" is contrived and artificial. It is, he can say, not a "real" problem.

A computer, though, would argue otherwise. For computers, fulfilling a condition and stopping is solving a problem. Generate random numbers and stop after finding one that's a certain size? Well, that's a problem for a computer. Create two possibilities, one that goes into a loop and another that stops? Yep, again if the computer stops, it will say it's solved a problem.

Which is what distinguishes Alan's computable problem from something more philosophical. And naturally we can take comfort that a human brain is more than just a sufficiently complex computer.

Or is it?

Maybe we should compute on that a little.

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 to all writers. 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

"Does Gödel Matter? The romantic's favorite mathematician didn't prove what you think he did.", Jordan Ellenberg, http://www.slate.com/id/2114561/. Jordan is professor of mathematics at the University of Wisconsin and points out that most mathematicians work with equations like "2 + 2 = 4" rather than (x)~Bew(x) which is what Kurt did. Under most definitions of the concept "number", then "2 + 2 = 4" is always true and you can prove it. So Kurt proved there are equations which don't do anything other than say they can't be proven? Many mathematicians simply say "Who cares?" and get back to work.

CooperToons has indeed found that many mathematicians don't seem particularly interested in Kurt's theoem. On occasion he's asked Ph. D. mathematicians to clarify points in Godel's work. The responses range from a rolling of the eyes as in "Oy, vey! No Godel again!" to "Dunno. Go ask a logician".

"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