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:
An We assume the machine is programmed so that any expression that the machine can print will be printed sooner or later. By the By a
Informally; So we define We define We call and 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 Now, suppose Not necessarily. If [Whether the machine can print expressions that are not sentences at all is immaterial. The important thing is that among the So --- Is it possible that the machin can print all true sentences? The answer is
By the definition of " 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 Let us further observe that the sentence
is an example of a sentence 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: "
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

Home Page