Tuesday, November 08, 2005

Godel, Escher, Bach: 7 months later

I started reading Godel, Escher, Bach, in May of 2005. As I have finished reading it today, I think the best sentence that summarizes the book is the one of the back cover:

"Every few decades an unknown author brings out a book of such depth, clarity, range, wit, beauty and originality that is recognized at once as a major literary event. This is such a work."
-Martin Gardner, Scientific American

This book is the only math related book that has ever won a Pulitzer prize, hence my interest to it. It combines knowledge from mathematics (Godel), painting (Escher), music (Bach) together with computer science and biology in order to tackle the questions: How can intelligence arise? Can we just put some hardware together and program it and it will start behaving intelligently? How can we as humans have consiousness?

Godel's incompleteness theorem plays a vital role in that journey to answer those questions. The best thing I got out of this book is an explanation on how Godel's theorem can arise - it had been haunting me since almost high school when I first read about it, and now I have found the most easy way (I think) to understand it. Remember that Godel's theorem states that there is no mathematical system that all theorems can be proved - there will be unproced theorems. But how did Godel prove that? Here is why, juts by looking at this painting.

The message reads "there is no pipe". On first view, the message seems wrong: the pipe is right there, and we know it. On second view, the message is right when you consider that the message may be referring to the whole painting instead, hence it is correct since the painting is not a pipe obviously.

That is the heart of Godel's theorem: you can have a phrase that can be interpreted in two levels, first inside the system, and second if you look outside the system and then it has a different meaning. But what does this have to do with math?

All formal systems in math can be translated into numbers. Every sentence can coprrespond to a number, a code if you wish. For example, the statement 1+1=2, can be translated to 166619992, is you set that '+' is represented by 666 and '=' by 999. That can be done in some way for ANY system.

Exactly because all symbols and statements can be represented by numbers, how can you distinguish whether a number is a symbol or a real arithmetic? For example, in the statement 666+333=999, which would be translated to 666666333999999 according to our simple code, how do you know whether 666 is the number 666 or is it the symbol '+'? If you look inside the system, it has to be a number; however if you look the painting/statement from the outside, the numbers have a second, dual meaning since they can represent a symbol. In the same way that in the painting we cannot tell whether the phrase "Ceci n'est pas une pipe" refers to the pipe inside the painting or to the painting as a whole, in exactly the same way a number we cannot tell whether it refers to the numerical value or to a symbol of number theory.

This is the heart of Godel's proof, the self-reference to something that can be interpreted in at least 2 different ways. Godel proved that no matter what system you use, and no matter what coding you use, there will be a statement that cannot be proved because you cannot tell where is it referring at! And that is a property of all formal systems in math, since all formal systems can be re-written with number-coding.

This type of self-reference also appears into Bach music ( I got the CDs!) and Escher's paintings. Hofstadter (author) brings everything together and argues that this type of reference causes also intelliegence to arise. Of course his arguments do not prove anything for sure, but they point at an interesting direction that may as well be true.

I always read book during flights and airport waiting. Since I bought this book, I went to Tennessee, Greece, Ithaca, twice in New York, and Colorado. It took me so long to finish because it is 700 pages long and also at several points it is not simple in writing: you have to focus and read the math carefully, take some time to solve the problems he poses, and make sure you understand everything. Sometimes he over-argues the same things again and again, but I think that's necessary for the ideas to stay in mind (reduduncy is good, as Patrick would say).

Anyways, now that I'm done with it, I have to start another book. A NY trip maybe is coming up, plus the long journey to Greece for Xmas. Feynman, maybe?