Godel, Escher, Bach

Part 1 - Godel's theorem.

Godel, Escher, Bach ( GEB ) is the author's personal attempt at understanding the evolution of life, intelligence, intuition, free will and many other question which have puzzled philosophers, biologists, mathematicians, AI developers and such. At the essence of his book lies a very deep and unsettling mathematical discovery - The Godel's incompleteness theorem, and much of the analogies he draws find their root back to this theorem. Hence, I'll first try to describe what this theorem means.
Mathematics is a form of systematic reasoning composed of axioms and theorems. Essentially, all other sciences use math as their base to perform derivations, and to try and explain the real world. Math is what's supposed to be the constant, unfaltering, all powerful tool which settles all disputes by unambiguous method of "proof". The story is that this axiom-theorem approach has what appears to be a big gaping hole in it. It turns out that if the theory is sufficiently complicated then there exist true statements which cannot be derived from the axioms. And if you try to include that in your set of axioms, then you can prove a theorem which will contradict the axiom. In this sense all formal systems are logically either incomplete or inconsistent.
What are formal systems?
Well, lets look at a system which uses three symbols - 'P','Q' and '-'. Here are the axioms
1) xP-Qx- is an axiom when x contains hyphen's only. ( for e.g. ---P-Q---- is an axiom )
2) Suppose x,y,z are all strings containing hyphens and xPyQz is a theorem, then xPy-Qz- is a theorem.
( Ok. I'll give this to you. Interpret the axioms by assigning the meanings "plus" and "equal" to P and Q. )
By using this we can generate many strings ( --P-Q--- is an axiom (1) and --P--Q---- is a theorem ( applying (2)))
( Given 2+1=3, this theorem proves that 2+2=4 etc )
So, this is fairly simple - we have a bunch of strings which can be generated and many more which cannot. For instance apply 2+2=4 again on (2) and you get --P---Q---- meaning 2+3=5 and so on. Observe how we can never produce a string like --P-Q- ( 2+1=1 ).
By successive application of the generated theorems on (2), we generate more theorems. And all these theorems are true ( as in they can be proved from their axioms ). In a nutshell this a what a formal system looks like. The point to note here is that this is not a sufficiently complex formal system. It is a truth-producing system but very limited in scope. You can easily see how formal systems could get more complicated. Our entire number theory ( additive axioms x+0=x, multiplicative axioms x*1=x, commutative axiom a+b=b+a etc ) has been formalized in these formal systems (Peano arithmetic et. al ). In GEB, the author comes up with a what he calls Typographical Number Theory (TNT) ( which is way more complex than the p-q system - containing many more symbols and much longer strings to express truths ). But like the previous system this also churns out strings of symbols which are true statements. So, this entire TNT is like a big bucket of strings which are either axioms or theorems generated by successive application of these axioms. Now what Godel's theorem says is that there exists a string outside this bucket which is true in this system. The obvious question is "what does true mean, if it is not generated from axioms". Well, it means, that this statement and the negation of this system both lie outside the bucket. Basically, in pq system, if I give you a string, you can immediately tell me whether it is a valid string. ( For e.g -PQ---, -P-Q---, PQ, PQRT are all invalid strings and -P-Q--, -P--Q--- are valid strings ), i.e you can tell whether a given string falls in the bucket or outside it.
But, as it turns out, when systems get sufficiently complex and cross a threshold, you cannot make this distinction anymore. This threshold level occurs when systems start talking about themselves. When self-reference is brought into play, for e.g ( suppose PQ system had a string which would answer the question of whether -P--Q----- was a theorem in PQ system). I know in the PQ system, such a string is not possible, but in "sufficiently" complex systems, such strings are possible. In these systems it becomes possible to write strings which say "I am not a theorem of TNT". Then it becomes impossible to assign a truth value to these strings. Quite like the Epimendis paradox "This statement is false" cannot be assigned a truth value. Another statement - "TNT is consistent" when codified into TNT as a string turns out to be a non-theorem of TNT ( falls outside the bucket ), as long as TNT is consistent. The process of codifying such statements into strings in the system is through the process of Godel numbering, which I will not describe here.
OK. So where is the catch?
The catch is to realize that systems, much like humans, though being excellent in stating truths about the world in general, become pretty weak when trying to talk about themselves. The realization is this : when a system has the power to mirror itself in it, i.e it becomes possible to write meta-theorems ( theorems about theorems etc ) in it, the layers in the system become entangled, where a statement means a truth in the one layer and false in the other, making even the most powerful systems collapse. Godel's Incompleteness theorem is a way to telling us that even mathematics cannot inspect itself from the outside. In reference to the system that you are a part of, your attempts to describe the system from the "inside" will always result in an incomplete analysis ( with some truths left out ) however hard you try to look at it from the outside.
Douglas R. Hofstadter describes the struggle to understand this from various perspectives. Some version or the other of this message can be found in Zen Buddhism, paintings by M.C. Escher, music by Bach ( although the music remains alien to me ). With this as the basic idea in mind, the journey in the book takes the reader through the realms of the genetic code to artificial intelligence. The quest to find where intelligence resides, whether the transistors in a CPU, or the neurons of the brain, whether the Operating system of a PC or the mind of a person. The entire book is sprinkled with allusions and isomorphisms to the Godel's theorem and the author believes that the concept of Strange Loops or Tangled Hierarchies is what lies at the core of life.

I'll follow up on this post soon, with many more profound observations ( Author's, not mine ), but if this was not impetus enough, I shall explicitly ask you to please go pick up this book and study it ( yeah! it makes for a pretty heavy read ).