World's shortest explanation of Gödel's theorem
We have some sort of machine that prints out statements in some sort of language. It needn't be a statement-printing machine exactly; it could be some sort of technique for taking statements and deciding if they are true. But let's think of it as a machine that prints out statements.
In particular, some of the statements that the machine might (or might not) print look like these:
P*x (which means that the machine will print x) NP*x (which means that the machine will never print x) PR*x (which means that the machine will print xx) NPR*x (which means that the machine will never print xx) For example, NPR*FOO means that the machine will never print FOOFOO. NP*FOOFOO means the same thing. So far, so good.
Now, let's consider the statement NPR*NPR*. This statement asserts that the machine will never print NPR*NPR*.
Either the machine prints NPR*NPR*, or it never prints NPR*NPR*.
If the machine prints NPR*NPR*, it has printed a false statement. But if the machine never prints NPR*NPR*, then NPR*NPR* is a true statement that the machine never prints.
So either the machine sometimes prints false statements, or there are true statements that it never prints.
So any machine that prints only true statements must fail to print some true statements.
Or conversely, any machine that prints every possible true statement must print some false statements too.
2 comments
First, to clear up one detail - we're making no requirements as to what the machine must print: it /could/ print NPR*NPR*, but in doing so it would be printing a false statement, because it's just done what it said it'll never do.
Conversely, if it never printed NPR*NPR*, there would be true statements that were never printed.
The reason this is a big deal is because it can be transformed directly to apply to several other systems: notably formal mathematics and conventional computers.
When applied to maths, Gödel's theorem shows that either valid maths can produce incorrect results, or that there are correct results that valid maths can never prove.
When applied to computing, it shows that there is no way to tell if an arbitrary calculation will ever finish.
http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem
