BOOKS: What I Learned from ‘GODEL, ESCHER, BACH’ – Part I

In keeping with UNESCO’s World Book Day which came to pass yesterday, I would love to revise my concepts from Gödel, Escher, Bach: An Eternal Golden Braid. They book first published in 1979, won for its author, Douglas Hofstadter, the Pulitzer Prize (1980) in non-fiction.  GEB may give the appearance of being a fun book, about music, art, computers, riddles and puns, but it is not just that. Using observations  from the diverse fields of math, language, and genetics, the book actually introduces very innovative concepts in an attempt to explain the nature of human thinking and intelligence.  The art of Escher and the compositions of Bach are actually referred to as analogies to help illustrate the highly abstract ideas presented. The inventiveness and originality of the author makes  the book a joy and a treasure in many ways. It is surely a book one would repeatedly return to.

So as a tribute to i) the love of books, ii) Gödel, Escher, Bach: An Eternal Golden Braid, and iii) Douglas Hofstadter, here is my attempt at summarizing what I learned from GEB.

Here we go…

In order to understand intelligence the GEB way, we first need to get certain key concepts straight. These concepts are “self-reference”, “paradox”, “recursion”, “isomorphism”, and “symbol”. As we whirl between and across these concepts, the view of intelligence a la Hofstadter will gradually emerge.

Self-reference and paradox

Sentences that talk about their own selves and people reflecting upon themselves are examples of self-reference. A typical example will be

This sentence is false.

Now if this sentence is really false, then it means the sentence’s claim is true. So it turns out that the sentence is actually true. But how can it be true when  it is false….?

Now here we are caught up in a looping paradox! If it’s false, it means it is true; but if its true it means it’s false!

Lesson? When a system that represents  meaning starts  referring to itself (and it can and it will) it will lock itself into a loop.  Each ‘level’ of  the loop is constantly leading up to the other and there’s no way out of it … an infinite regress! This is what Hofstadter calls a Strange Loop – a  concept he brings out more fully in his latest book I am a Strange Loop. (See Here for an interesting anthology of paradoxes.)

Paradoxical Mathematics…!

What!!#!@!!

Math…..paradoxical? Well… Kurt Gödel, a young Austrian mathematician, proved that.

Gödel used Bertrand Russell and Alfred Whitehead‘s system of formal mathematics (from their book called Principia Mathematica) to show that it contains irresolvable inconsistencies in the spirit of the paradox stated above.

Any formal system of mathematics attempts to show that i) all mathematical truths (or theorems) are derivable through strict rules of logic from previous truths (initial truths from where the derivations are build up are taken as true a priori and are called as axioms) [completeness] and that ii) no mutually contradicting statements are derivable in the system [consistency].

On the other hand, Gödel proved how sufficiently strong and expressive formal systems cannot prove their own consistency (provided that they are in fact consistent).

How did he do it?

First of all, he devised a system of numbers to represent statements in formalized mathematics. Next, he assigned these “Godel numbers” to steps in derivation of the theorems of the math system. He found that these strings of Gödel numbers can themselves be derived through the rules of math just like the actual derivations of theorems. For every logical rule applied in the derivation, a corresponding mathematical rule will yield the very Gödel number that represents the next step of the derivation. Thus Gödel discovered a heretofore undiscovered level of meaning in the formal system.

But where is the paradox?

Gödel showed how this process of “Gödelization” can be used to construct the following paradoxical statement in terms of the formal system.

This theorem cannot be proved in this system.

Now if the concerned system of formal math is REALLY complete (i.e. able to provide logical proofs to all its theorems) then a proof for the above statement will automatically prove the system’s inconsistency (as the system now proves a contradictory statement). On the other hand, the inability to prove the statement (indeed that is the case) is evidence  of the INCOMPLETENESS of mathematical logic!

Herein lurks another paradoxical self-reference – a Strange Loop!.

Essential incompleteness and Recursion

Paradoxical statements like these defy the neat categorization of ‘truth’ and ‘false’. In fact, truth and falsehood seem to be constantly leading to each other in a continuous fashion. This is the strangeness of the loop and it involves a process of recursion.

Recursion is a procedure which entails repeating its own steps indefinitely. The shampoo instructions

1. Lather; 2. Rinse; and, 3. Repeat.

are recursive. If acted upon literally, there will be a continuous repetition of the procedure making your stay in the washroom infinite! Hence, recursion is a self-reference with a potentially infinite continuity.

A common and visual example of recursion is when you are standing between two large mirrors….  “endless corridors” (a term used by Hofstadter in I am a Strange Loop) on both sides!

Some other visual examples of recursion are as follows:

A picture embedded inside itself inside itself inside itself…

Example of a fractal pattern made using a recursive math equation

Waterfall - Lithograph by Escher (1961)

Example of a pattern resulting from a video feedback loop, from the cover of “I am a Strange Loop”

The last example most closely illustrates the concept of a Strange Loop. When successive iterations of the recursive process are designed to have a slight variation, novel and complicated patterns emerge from the  starting and much simpler ingredients. The  patterns could never be predicted by looking at the starting levels alone.

Hofstadter presents an illustration of recursive cognitive processes by referring to the chess situation. Before making the next move in a game of chess, you would like to see with your mind’s eye how will the opponent respond to the move you are now considering. You may also try to “look ahead” further into the game by trying to determine a possible move against the opponent’s response to your next move and then again reflect on how the opponent will respond to that…. This process of repeatedly generating solutions belonging to a particular class (in math, members of a particular set such as the Fibonacci numbers) is called as recursive enumeration.

Hofstadter seems to suggest that a recursively defined set of procedures entails an increasing level of complexity of behavior. Furthermore, where a machine (for e.g., a computerized chess program) must be given a decision procedure to settle on a solution rather than engage in an infinite “looking ahead”, humans have the capability to “jump out of the system” at their will. They can put a break on the recursion, observe the workings of their  own reasoning process, draw some conclusions, and look for alternatives. Hofstadter illustrates his point beautifully by engaging his readers in a task involving recursive enumeration in the first chapter of his book. (For a go at the task, check out this site.)

The human ability to stand back and observe the results of their own thinking guarantees an unpredictability of ideas and behavior that the machine lacks. Ultimately, it is these strange loops of thought that are also responsible for the general self-consciousness that defines the human condition. Akin to the beautiful, totally unpredictable and unique pattern that emerges out of a video feedback loop.

There is so much more still left to delve into…

I’ll complete this summary of my GEB concepts in the next post InshaAllah.