Here's my attempt:

Gödel figured out how to encode the statement "you can't prove me" as an arithmetical expression. Minds blew.

Wow, that was a disappointment. I've always thought of Gödel's incompleteness theorem as something so arcane that I'd never understood it. Now it turns out to be both trivial and really similar to the Halting problem.

Good explanation though.

Okay. I have a problem maybe someone can help me with.

The article says:

"If the machine prints NPRNPR, it has printed a false statement. But if the machine never prints NPRNPR, then NPRNPR is a true statement that the machine never prints."

This part seems logically true:

"If the machine prints NPRNPR, it has printed a false statement." It seems logically true, and I wont say why because I view it as obvious =/

This part seems logically false:

"if the machine never prints NPRNPR, then NPRNPR is a true statement" I don't understand the logic of "If it is not printed, it is true." I was under the impression that the only true statement was "If it prints, then it is true", and of course the contrapositive: "If it is not true, it doesn't print". The statement taken from the article is NOT the contrapositive. It is the inverse, and because the converse of a statement is not always true, the inverse is not always true because the inverse is always equal to the converse. "if the machine never prints NPRNPR, then NPRNPR is a true statement" That statement is the inverse of the original if-then statement, and the inverse/converse is FALSE because it allows opportunities which violate the original if-then statement.

I logically concluded that the statement in the proof:

"if the machine never prints NPRNPR, then NPRNPR is a true statement" is a false statement. And therefore the proof is incorrect.

Okay. If I am wrong, can someone please tell me where?

undefined

undefined

Gödel's theorem:

If you print only true statements, you can not print all true statements. Proof:

"I do not print this statement"

While we're on the topic, something that always puzzled me: doesn't Gödel's theorem apply only to 'non-trivial' axiomatic systems?

Meaning you could come up with a trivial system to which it doesn't apply. Which begs the question: How do you define triviality here?

From the article, "Either the machine prints NPR@NPR@, or it never prints NPR@NPR@."

This makes sense in that the machine has told itself never to print NPR@NPR@ in the future.

It would be like trying to verify someone doesn't know a secret by asking them about the secret they shouldn't know.

Zero knowledge proofs come to mind.

And that's probably a good description of my knowledge on this subject.

edit: changed asterisks to @ because HN doesn't display asterisks.

The article in Wikipedia is pretty good, although stops short of the full details. In particular it addresses this question of the Liar's Paradox versus Gödel's theorem "proper".

http://en.wikipedia.org/wiki/Goedel%27s_incompleteness_theor...