The Science of Comprehension

How We Understand Abstract Concepts

Part IV—A

(Optional)
Conceptual Overview of Gödel's Incompleteness Theorem

I'll digress here a moment and give a brief conceptual overview of Gödel's proof here so anyone who decides to further pursue this will already have been introduced to some of the important concepts used in the proof.

Gödel essentially showed that given any formal mathematical system with the natural counting numbers 1,2,3,..., where the natural counting numbers have their usual symbolic meaning of "how many," it was always possible to come up with a completely different "symbol interpreter", where each number did not have it's usual meaning of "how many," but instead each number was interpreted by this new "symbol interpreter" as being a symbol for a mathematical statement. In this system the number 5 doesn't mean "five things" but instead is a symbol for some equation, such as "1+1=2".

If you're familiar with computer programming and the ASCII table, then consider how every equation which can be typed into a text editor is represented internally by a sequence of numbers, where each number is the ASCII number for that character.

ASCII   TABLE
32               51 3             70 F              89 Y             108 l
33!52471G 90Z109m
34"53572H 91[110n
35#54673I 92\111o
36$55774J 93]112p
37%56875K 94^113q
38&57976L 95_114r
39'58:77M 96`115s
40(59;78N 97a116t
41)60<79O 98b117u
42*61=80P 99c118v
43+62>81Q100d119w
44,63?82R101e120x
45-64@83S102f121y
46.65A84T103g122z
47/66B85U104h123{
48067C86V105i124|
49168D87W106j125}
50269E88X107k126~


For example, the string "1+1=2" is represented internally by the numbers: {49, 43, 49, 61, 50}

Symbols: 1 + 1 = 2
Numbers: 49 43 49 61 50

Then, instead of thinking these as five separate numbers, push the numbers together to get one huge number. This huge number represents the equation:

Symbols: 1 + 1 = 2
Numbers: 49 43 49 61 50
Gödel #: 4943496150

This isn't exactly the way Gödel did it, but I hope it gets across the conceptual idea that every equation can be converted to a unique number. This unique number is known as the equation's “Gödel number”.

The process also works in reverse — every Gödel number can be converted back to the corresponding equation it represents. In our example above we just run the steps in reverse:1
  1. Starting with the huge number 4943496150
  2. Break the number into its parts: 49 43 49 61 50
  3. Referring to the ASCII table, translate each number to the corresponding symbol it stands for:
    49
    		 → 1
    43
    		 → +
    49
    		 → 1
    61
    		 → =
    50
    		 →
    		 2
The equations themselves do not necessarily have to be true. There are numbers for equations which are false. There is a number for the statement "1+1=5". This statement is false, but we can still write it down, and if we can write it down, then it can be converted to a unique number. There are also numbers for equations which don't make any sense, such as "=1+-". Even though this statement does not make any sense, we can still write it down, and again if we can write it down, then it can be converted to a unique number. Likewise, any number can be converted to a mathematical statement, even if the resulting statement doesn't make any sense.

We now have two "Symbol Interpreters" which can both interpret the symbol "4943496150":

Symbol Interpreter A: "4943496150" means→"how many"
Symbol Interpreter B: "4943496150" means→"1+1=2"

Thus a mathematical statement containing "4943496150" can be interpreted in two ways. It could be interpreted in the usual way as representing a particular "how many" type number, or, it could be interpreted in a Gödelian way as referring to the mathematical statement "1+1=2". Thus it is possible for a statement within a mathematical system to be interpreted as talking about another statement within the system itself. Gödel invented a symbol interpreter which makes it possible for statements within the system to be interpreted as talking about other statements within the system.

Hofstadter writes:
"This unexpected double-entendre demonstrates that our system contains strings which talk about other strings in our system. And this is not an accidental feature, it is just as inevitable a feature as are the vibrations induced in a record player when it plays a record. It seems as if vibrations should come from the outside world -- for instance, from jumping children or bouncing balls; but a side effect of producing sounds — and an unavoidable one — is that they wrap around and shake the very mechanism which produces them."2

If a statement can be interpreted as talking about another statement within the system, is it then possible to come up with a statement which talks about itself? It takes a bit of work, but yes, turns out it can be done. There does exist within the system a statement, in fact an infinite number of statements, which essentially talk about themselves. Patterns of symbols in a formal system can be interpreted as talking about themselves. These patterns have, in a way, achieved self awareness.3

PREV          NEXT


Science of Comprehension Index

Back to Deley's Homepage


Endnotes:

1 Again this isn't the method Gödel used. The actual Gödel numbering scheme is a bit more complex.

2 Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid. A metaphorical fugue of minds and machines in the spirit of Lewis Carroll, p 270. (The book's subtitle isn't very helpful in describing what the book is about.)

3 It's also quite possible, even likely, that I don't know what I'm taking about.