A Gödelian Puzzle (The Variant)
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". A previous page presents an anotation of that, while this page presents A Variant that Dr. Smullyan also presents. | Consider another computing machine that prints symbols. The machine can only print expressions composed from the five symbols: ~ P N 1 0 In this case we represent the Natural numbers in binary notation then you can get them all by just using strings of 1's and 0's. Every expression is assigned a number called the Gödel number of the expression. The scheme to make this assignment is to assign each of the five symbols a Gödel number as follows: ~ gets 10 The Gödel number of a compound expression is created by replacing each symbol by its Gödel number -- for example PNP would have the Gödel number 1001000100. We next redefine norm of an expression to be the expression followed by its Gödel number -- For example the norm of PNP is the expression PNP1001000100. A sentance is now an expression of one for the four forms: (1) PX In the above X is any number written in binary form. Now PX is true if X is the Gödel number of a printable expression. We call PNX true iff X is the Gödel number of an expression whos norm is printable. We call ~PX true if PX is not true (X is not the Gödel number of a printable expression. ~PNX true iff PNX is not true. Again we are given that the machine never prints a false sentence. And again we are tasked with finding a true sentence that the machine cannot print. (5) ~PN101001000 You can see that the digits following the symbols ~PN make up the Gödel number of ~PN thus the entire string is the norm of ~PN. and it is the same as (5) in the previous page that did not use numbers. |
This Page Last Updated - Thursday, March 23, 2006 12:02:57 -0500
Home Page