A Gödelian Puzzle
A Discusson Of The First Few Pages Of "Gödel's Incompletness Theorems" by Raymond M. Smullyan
In the frist few pages of this book Dr. Smullyan presents what he calls a "Gödelian Puzzle". Here is an antonated version of that content.
Consider a computing machine that prints symbols. The machine can only print expressions composed from the five symbols:
~ P N ( )
An expression is any finite non-empty string of the above five symbols. An expression X is called printable if the machine can print it.
We assume the machine is programmed so that any expression that the machine can print will be printed sooner or later.
By the norm of an expression X, we shall mean the expression X(X) - e.g. the norm of P~ is P~(P~).
By a sentence, we mean any expression of one of the following four forms (where X is any expression):
Informally; P stand for "printable"; N stands for "the norm of" and ~ stands for "not".
So we define P(X) to be true if (and only if) X is printable.
We define PN(X) to be true if the norm of X is printable.
We call ~P(X) true iff (if and only if) X is not printable,
and ~PN(X) is defined to be true iff the norm of X is not printable.
We have now given a perfectly precise definition of what it means for a sentence to be true, and we have here an interesting case of self-reference: The machine is printing out various sentences about what the machine can and cannot print, and so it is describing its own behavior!
We are given that the machien is completely accurate in that all sentences printed byt he machine are true. For example if the machine ever prints P(X) then X really is printable (in other words X will be printed sooner or later). Also if PN(X) is printable, so is X(X) (the norm of X).
Now, suppose X is printable. Does it follow that P(X) is printable?
If X is printable, then P(X) is certainly true, but we are not given that the machine is capable of printing all true sentences but only that the machine never prints any false ones.
[Whether the machine can print expressions that are not sentences at all is immaterial. The important thing is that among the sentences printable by the machine, all of them are true.]
So --- Is it possible that the machin can print all true sentences? The answer is no and the problem for the reader is this: Find a true sentence that themachine cannot print. [Hint: Find a sentence that asserts its own non-printability -- i.e. one which is true if and only if it is not printable by the machine.]
By the definition of "true", this sentence is true iff the norm of ~PN is not printable (see sentence (4) above for the example). However, the norm of ~PN is the very sentence ~PN(~PN). And so sentence (5) is true if and only if it is not printable.
Thie means that either the sentence is true and not printable, or it is printable and not true. The latter alternative violates the given hypothesis that the machine never prints sentences that are not true. Hence the sentence must be true, but the machine can not print it.
Of course, instead of having talked about a machine that prints various expressions in our five symbols, we could lhave talked about a mathematical system that proves variouis sentences in the same five symbols. We would then reinterpret the letter P to mean provable in the system, rather than printable by the machine. Then, given that the system is wholly accurate (in that, false sentences are never provable in it), the sentence ~PN(~PN) would be a sentence that is ture but not provable in the system.
Let us further observe that the sentence PN(~PN) is false (sence its negation is true). hence it is also not provable in the system (assuming that the sytem is accurate). And so the sentence
is an example of a sentence undecidable in a system -- i.e. neither it nor its negation is provable in the system.
There is a grand article on Wikipedia about all this titled "Gödel's incompleteness theorems".
To get the full flavor of Gödel's result also consider "PageThree" which presents a variant of this puzzle.
In this discussion the computing machine is NOT said to be any special kind like (for example a Turing Machine).
The norm is a self referential operation.
There are only four sentences.
(1) says: "X is printable"
Smullyan goes on to say that this machine seems to be alive and that it is not surprising that among the folks who investigate AI (Artifical Intelligence) computers oare of great interest.
This is the kernel of Gödel's result when you assume that the system you are working with is consistent. That is: If the system is consistent then is is not complete.
Gödel's result also requires the system to be self referential.
These few paragraphs, along with the ones that immediately follow it represent what it means to say that a system contains undecidable statements.
There is an open question as to whether there are any non self referential undecidable statements. For a while Fermat's Last Theoream was considered to be in this catagory.
This Page Last Updated - Thursday, March 23, 2006 12:02:57 -0500