M's Gödel

Machine M thinks it's a real smarty pants that believes it will never print false statements and will eventually print all true statements. For the sake of argument, let's say it can print with at least the characters A-Z and *.

For example, M could print out ONE*PLUS*ONE*EQUALS*TWO, which could be a long-winded way of printing 1+1=2. Count that as a true statement.

ONE*PLUS*ONE*EQUALS*THREE ?
Count that as something M would never print if it's true to its belief that it will never print a false statement.

Now strings printed out by M of the following forms have particular meanings (M is "speaking" in the first person here):

P*x	"I will print x."
NP*x	"I will never print x."
PR*x	"I will print xx."
NPR*x	"I will never print xx."

For example, NPR*FOO means "I will never print FOOFOO." NP*FOOFOO means the same thing. If M ever did print both FOOFOO and NPR*FOO, then its belief in its truthfulness would be violated.

Now consider whether M would ever print

    NPR*NPR*      ("I will never print NPR*NPR*.")

If M does print NPR*NPR* at some point, it has printed a false statement.

But if M never prints NPR*NPR*, then NPR*NPR* is a true statement that M never prints.

So either M sometimes prints false statements, or there are true statements that M never prints!

Sorry, M. Not such a smarty pants after all.

*   *   *  

The above is derived from World's shortest explanation of Gödel's theorem, which relates all this to the limits of machines that produce only true statements in arithmetic.