Mike Kroh: Ok, I know it doesn't rhyme, but you went and mentioned the Halting Problem, so I have to talk about one of my favorite topics: Goedel's Incompleteness Theorems. One (weakened) form of Goedel's First Incompleteness Theorem can be proven using the fact that the Halting Problem is undecideable:

1) Consider all math and logic: it's a set of assumptions (e.g. "if x and y are sets which have the same elements, then they are equal - I know, real basic stuff) and rules for deriving things from those assumptions. (To read about the set of assumptions and rules, look up "ZFC" on Wikipedia).

2) Now consider the set of all true math/logic statements. We assume that:

a) Every true statement can be derived (using the rules of math/logic) from the basic assumptions (even if we don't know exactly how to derive it, if we can write it in math and it's true, then it can be proven starting with the basic assumptions and rules).

b) There are no true statements which contradict each other (you can't have both A and -A be true).

3) Now, since we can prove all the true statements, imagine we have an algorithm to generate all of them and assign each of them an index number (yes, they will be infinite, but the integers are infinite, so that's ok). Call the integer "n" and the algorithm "N()", so that if we put "n" into "N()", then we get the true statement "N(n)", whatever that may be (I'm not saying you have to know **what** you get out of it - just that if you put in an integer, you get back a true statement, and that all the true statements can be generated - time is not a factor here, BTW - this is math, not CS! But srsly, you can just say "every true statement will **eventually** be generated" if you think it takes time for an algorithm to return a result).

4) So keep all that in mind, but set it down for a second and imagine that we have a different algorithm "A()" and we want to know whether or not it halts on input "i". In other words, does "A(i)" halt? Yes, I know that we know you can't decide the halting problem (since "A()" is unspecified, it could be anything). But we still **want** to know whether or not "A(i)" halts.

5) We can express the statement "A halts on i" (or "A(i) halts") mathematically using something called "Kleene's T predicate" - just take it for granted that we can represent "A halts on i" using the language of math/logic. Write it "H(A,i)". I'm not saying that it's true or false, I'm just saying write it down (I can write 1+1=3, and we can prove the negation is true - but the point is you can write whatever you want, so write H(A,i) and know it is a mathematical representation of the sentence "A halts on i.").

6) So now, since we have the algorithm for generating all true statements ("N()"), that means there is some integer "n" we can input to "N()" so that "N(n) = H(A,i)" or else "N(n) = -H(A,i)".

7) Now, even though we don't know what that "n" is, the fact that it exists at all means that if we let the algorithm run long enough, then it will eventually hit "n".

8) Since it always hits "n", we can always decide whether or not "A()" halts.

9) Since we've kept things general (we haven't specified **what** algorithm "A" is), this means we have an algorithm to decide the halting problem.

10) Since we know that you can't have an algorithm to decide the halting problem, one of our assumptions must be false.

11) What were our assumptions?

2) Now consider the set of all true math/logic statements. We assume that:

a) Every true statement can be derived (using the rules of math/logic) from the basic assumptions (even if we don't know exactly how to derive it, if we can write it in math and it's true, then it has a valid proof).

b) There are no true statements which contradict each other (you can't have both A and -A be true).

12) That means at least one of (2a) or (2b) must be false(!!!).

13) What does this mean? It means that:

a) There are true statements that can be expressed mathematically which do not have valid proofs. (incomplete).

or

b) There are (simultaneously) true statements which contradict each other (both "A" and "-A" can be proven to be true). (inconsistent)

14) This holds for every axiomatic system in ZFC (which is all of the math and logic that you know and love).

15) BAM! Math is broken. Thanks, Obama! (j/k)

This was shamelessly paraphrased from the WP page on the Halting Problem (I've read G.E.B, so I know plenty about the Incompleteness Theorems, but they're complicated and I'm lazy, and I want to be correct).

If you want to know all about Goedel's Incompleteness Theorems (there are two) while having your mind blown to pieces, then you should read "Goedel, Escher, Bach: an Eternal Golden Braid" by Douglas Hofstadter. It will change your life (it did for me!).