Epimenides Or Liar Paradox
Jack Dikian
Dec, 2004
A Review of Douglas R. Hofstadter’s "Godel, Escher, Bach: An Eternal Golden Braid". Penguin Books 1980, ISBN0-14-005579-1.
What can Kurt Godel a mathematician, M.C. Escher an artist and Johann Sebastian Bach the famous composer have in common? Intending to write an essay about Godel’s theorem, Hofstadter gradually expanded to include Bach and Escher until finally he realized that the works of these men were in essence "shadows cast in different directions by some central theme". The book tries to reconstruct this central theme.
A single musical theme can be played against itself (by say having ’copies’ of the theme played by various participating voices) to create what is known as a canon. Songs such as "Frere Jacques" or "Row, Row, Row Your Boat" are examples of canons. "Frere Jacque" for example, enters in the first voice and after a fixed time delay, a ’copy’ of it enters, in not necessarily the same key. After the same fixed time delay in the second voice, the third voice enters carrying the theme, and so on. In order for the theme to work (as a canon theme), each of the notes must be able to serve as a dual (or triple, or quadruple) role: The notes must be part of a melody as well as part of a harmonization of the same melody. When there are three canonical voices, for instance, each note of the theme must act in two distinct harmonic ways, as well as melodically. Thus, each note in a canon has more than one musical meaning. The human brain will (well!) automatically figure out the appropriate meaning, by referring to context.
However, ’copies’ of the theme can be staggered not only in time, but also in pitch. The first voice might sing the theme starting on C, and the second voice overlapping the first voice, might sing the identical theme starting five notes higher, on G. It is also possible that speeds of the different voices might not be equal. That is, the second voice might sing twice as quickly, or twice as slow, as the first voice. The former is called diminution, the latter augmentation (since the theme seems to shrink or to expand). To complicate matters, it is also possible to invert the theme which means the second voice jumps down wherever the first theme jumps up, by exactly the same number of semitones.
Bach was especially fond of inversions, and they show up often in his work. Finally, the most esoteric of ’copies’ is the retrograde copy. This is where the theme is played backwards in time. It should be noted at this point that all the copies mentioned preserve all information in the original theme. The original theme is fully recoverable from any of the copies. The book is in fact full of "information preserving transformations" or isomorphisms. A fugue is like a canon, in that it is based on the theme which gets played in different voices and different keys, speeds, directions etc.
However, the notion of fugue is much less rigid than that of canon, and consequently it allows for more emotional and artistic expressions. Hofstader introduces us to the notion of "Strange Loops" for the first time by giving us an example of one of Bach’s musical offerings to the king called "Canon per Tonos". This theme has three voices with the lower of the voices singing in C minor. This is the key of the canon as a whole. What makes this theme different however is that when it concludes, or, rather, seems to conclude, it is no longer in the key of C minor, but now is in D minor. Bach has somehow changed keys right under the listener’s ear. It is also so constructed that the "ending" ties smoothly onto the beginning again only this time one key higher. After exactly six such modulations, the original key of C minor is restored. Hofstadter uses this as an example to illustrate the concept which he calls "strange loops". Here he says "The strange loop phenomenon occurs whenever, by moving upwards, or downwards through the level of some hierarchical system, we unexpectedly find ourselves right back where we started.". Strange loops occur over and over again in this book.
For many years, mathematicians were among the first admirers of Escher’s drawings. Hofstadter explains how one of the most powerful visual realizations of the notion of strange loops are presented in the work of Escher. Many of the drawings have their origins in paradox, illusions, or double meaning. However, strange loops are the most recurrent themes in Escher’s work. Escher’s 1961 lithograph "Waterfall" is compared to Bach’s "Canon per Tonos". The Waterfall is an illustration of a six-step endlessly falling loop. The concept of "Loop Tightness" is introduced by comparing it to levels in the strange loop. For example, both Bach’s "Canon per Tonos" and Escher’s "Waterfall" are six-step strange loops. As the loop is "tightened", the example of the "Drawing Hands" is illustrated~ here each of the two hands draws the other: a two-step strange loop.
Finally, the tightest of all strange loops is realized in "Print Gallery". This is a picture of a picture which contains itself. Hofstadter asks; Or is it a picture of a gallery which contains itself? Or of a town which contains itself? Intuition senses that there is something mathematical involved in both Bach’s and Escher’s works. In fact, just as the Bach and Escher loops appeal to the very simple and ancient intuitions - a musical scale, a stair case - so the discovery, by Godel of strange loops in mathematical systems. Godel’s discovery (in its absolutely barest form) involves the translation of an ancient paradox in philosophy into mathematical terms.
The statement, "This statement is false", is usually considered a fair demonstration of the Epimenides Paradox. If you tentatively think it is tree, then it immediately backfires on you and makes you think it is false, but once you decide it is false, a similar backfiring returns you to the idea that it must be true. The Epimenides paradox is a onestep strange loop, like Escher’s Print Gallery. But how does it have to do with mathematics? That is what Godel discovered.
Godel’s idea was to use mathematical reasoning in explaining mathematical reasoning itself. This notion of making mathematics "introspective" proved to be enormously powerful. Godel’s greatest work resulted in "Godel’s Incompleteness Theorem". Godel’s theorem appears as proposition VI is his 1931 paper "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I" It states: To ever w-consistent recursive class k of formulae there corresponds recursive class-sign r, such that neither v Gen r nor Neg(v Gen r) belongs to Fig(k) (where v is the free variable of r). This was actually presented in German, and you may feel that it might as well be in German anyway. Another attempt; A paraphrase in "English":- All consistent axiomatic formulations of number theory include undecidable propositions.
The proof of Godel’s incompleteness theorem hinges upon the writing of a self referential mathamatical statement, in the same way as the Epimenidies paradox is a self-referential statement of language. But where it is very simple to talk about language in language, it is not at all easy to see how a statement about numbers can talk about itself. The difficulity arises when we consider that mathematical statements (Number theoretical) are about properties of whole numbers. Whole numbers are not statements, nor are their properties. A statement of number theory is not about a statement of number theory; it just is a statement of number theory. Godel had the insight that a statement of number theory could be about a statement of number theory, if only numbers could somehow stand for statements. The idea of a code was therefore emerging. In the Godel code, usually called "Godel-Numbering", numbers are made to stand for symbols and sequence of symbols. Each statment of number theory, being a sequence of specialized symbols, acquires a Godel number, something like a telephone number, by which it can be referred to. This coding scheme allows statements of number theory to be understood on two different levels. As a statement of number theory, and also as statements about statements of number theory. Godel finally transplanted the Epimenidies paradox to the statement:
"This statement of number theory does not have any proof"
or more correctly,
"This statement of number theory does not have any proof in the system of Principia Mathematica"
where is the Epimenides statement creates a paradox since it is neither true or false, the Godel sentence is unprovable inside P.M but true. Hofstadter proceeds to place Godel’s work in its historic background. Russell’s, Grelling’s, Whitehead’s and Hilberts works are touched on.
I know of no better explanation than this book presents of what Godel achieved and of the implications of his revolutionary discovery. That discovery concerns in particular recursion, self-reference and endless regress, and Hofstadter weaves the three themes mirrored in the art of Escher and the music of Bach. Each chapter is preceded by a kind of prelude which early in the book takes the form of a "Dialogue" between Achilles and the Tortoise (from Zeno of Elea). Almost all concepts are presented twice. Firstly, metaphorically in the Dialogue, yielding visual images. These then serve, during the reading of the following chapter, intuitive background for a more serious and abstract presentations of the same concept. Each Dialogue is patterned on a composition by Bach. For example, if the composition has three voices, so does the corresponding conversation. If the composition has a theme that is turned upside down or played backwards, so does the particular conversation. Each dialogue states, in a comic way (Lots of word play), the themes that will be further explored in the chapter that follows.
The book is packed with examples of strange loops, loops that exemplify the self reference that is one of the book’s central themes. For example consider the following impossibility:-
The following sentence is false
The preceding sentence is true
Taken together, the sentences have the same effect as the original Epimenides paradox (or reminiscent of Drawing Hands), yet separately, they are harmless. Nevertheless, we who see the "picture" or statement as a whole can escape the paradox by "Jumping" out of the "system" to view it from a meta- level, just as we can escape the traditional paradox of logic by jumping into a meta-language. Hofstadter introduces modem mathematical logic, computability theory, Feynman diagrams for particles that travel backward in time, Fermat’s last theorm, Turing machines, computer chess, computer music, expert system on the simulation of Natural languages, molecular biology and many other fascinating topics. The book’s discussion of artificial intelligence is also stimulating. Does the human brain obey formal rules of logic? He believes no computer will ever do all a human brain can do until it somehow reproduces that hardware°
Formal systems are discussed and the reader is urged to work out a puzzle to gain familiarity with formal systems in general. Fundamental notions such as "theorem", "rule", "inference" etc are introduced. The idea of recursion is presented in various contexts. These include musical patterns, linguistic patterns, mathematical functions, computer algorithms etc. The proceeding Dialogue ("Little Harmonic Labyrinth") to the section on recursion is about stories within stories. The frame or outer story is left open, instead of finishing as expected, thus leaving the reader dangling without resolution.
A discussion of how meaning is split among coded messages is found with examples including strands of DNA and undeciphered inscriptions on ancient tablets. The relationship of intelligence to "absolute" meaning is postulated. In the proceeding Dialogue, Achilles and the Tortoise try to resolve the question, "which contains more information ~ a record, or the phonograph which plays it". A chapter discusses the ideas of Zen Buddhism. Hofstadter suggests that in a way, Zen ideas bear a metaphorical resemblance to some contemporary ideas in the philosophy of mathematics. Godel’s theorem is visited. Brains and Thought is the title of chapter XI. Here, the question "How can thoughts be supported by the hardware of the brain" is asked. An overview of the large and small scale structure of the brain is given. The relationship between neural activity and concept is discussed.
The Church-Turing thesis, which relates mental activity to computation, is presented in several ways. These are analysed in view of their implications for simulating human thought mechanically. A discussion of the famous "Turing test" opens a chapter on Artificial Intelligence. A Dialogue is found where the idea of how we unconsciously organize thoughts so that we can imagine hypothetical variants on the real world all the time makes the subject matter. The book closes with a wild dialogue which is simultaneously patterned after Bach’s six-part Ricecar and the story of how Bach came to write his musical offering. In his dialogue, the computer pioneers Turning and Babbage improvise at the keyboard of a flexible computer called a "smart-stupid" which can be as smart or as stupid as the programmer wants. Turning produces on his computer screen a simulation of Babbage. Babbage however, is seen looking at the screen of his own "smart-stupid", on which he has conjured up a simulation of Turning. Each man insists he is the real and the other is no more than a proposed program. An effort is made to resolve the debate by playing the Turning game, which was proposed by Turning as a way to distinguish a human being from a computer program. At this point Hofstader himself walks into the scene and convinces Turing, Baggage and all the others that they are creatures of his own imagination.
No comments:
Post a Comment