Review of Chapters XVI and XVII with Dialogues in Gödel, Escher, Bach: An Eternal Golden Braid Final version

Kai-Mikael Jää-Aro
NADA

Edifying Thoughts of a Tobacco Smoker

In the Dialogue, Achilles visits the Crab and admires his recently acquired Magritte paintings---or are they really paintings? The Crab takes out and smokes the pipe in The Shadows (and later puts it away in The Air and the Song) and offers the cigar in State of Grace to Achilles, who however declines, slightly dizzied by this unnatural behaviour of the paintings...

The Crab recites a poem by J. S. Bach about the pious thoughts awakened in his mind when watching the curls of smoke rising from his pipe.gif

In my opinion, the really edifying thoughts of a tobacco smoker should arise from contemplation of chest X-rays...

The Crab turns out to write poems of his own and plays a recording of a pseudo-limerick for Achilles.gif

The record player the Crab uses is his latest invention in his battle against the Tortoise. In Contracrostipunctus the Tortoise mentioned that the Crab had commissioned a self-reassembling Record Player Omega but due to the Tortoise's sudden sleepiness we were not told how it had fared. Now it is revealed that the tortuous Tortoise indeed had demolished that one as well, since the reassembly controller had to stay constant and thus was subject to the fatal vibrations. But the Crab, while reading Gebstadter's book on metal-logic, Copper, Silver, Gold: an Indestructible Metallic Alloy, ran upon a description of viruses and noted that they have the ability to ``spontaneously self-assemble from their component units'' and thus do not need any reassembly controller.

A spontaneously self-assembling phonograph is constructed, but the Tortoise yet again reduces it to smithereens. Now, this is rather curious, since for a ``spontaneously self-assembling'' entity it should not matter if it is reduced to its component units, as these should just crawl together and rebuild the original unit (those who have seen the movie Hardware know what it would look like). Hofstadter is really straining the analogy here (for, in spite of his use of the term ``isomorphism'', he is really making analogies), but of course ``component units'' are not really atomic as we have noted for example with real atoms (we are making an analogy here) which are not atomic either, but can be decomposed into smaller subunits that lose the identity of their previous aggregate. Thus, if the Tortoise manages to destroy the component units of the self-assembling phonograph, there no longer will be anything that can self-assemble.

Now, the Crab was almost as devastated as his phonograph and finally gave up on trying to get a record player that could play any and all sounds and instead tries to get a record player that will only play records it knows will not damage it, and this cautious phonograph is what now is standing before Achilles and the Crab. The Tortoise, in his ambition to always be one up on the rest of the gang (doesn't he remind you a lot of Skalman?), now instead tries to make records that will slip by the Crab's defences.

We note that Hofstadter leaves the analogy of record players as formal systems and instead introduces the analogy of record players as living organisms or even living cells, where the screening for malign records matches the immune system's screening for pathogenic microorganisms---viri in particular as these can subvert the reproduction apparatus of the cell.

The intellectually fleet-footed Achilles is fascinated by the television camera in the record player and the Crab takes it out and lets him play with it. He goes on to discover the interesting things you can do with a video camera if you point it at its own output---self-engulfing. (Do by all means try this at home kids, it's quite amusing.) The ``galaxy'' in figure 81.j has 13 spokes, which probably is interesting as it is a prime and does not correspond to any of the ``magic'' angles π/3, π/4, π/6, ... (and it is one more than the number of pictures on the spread).

After a while Achilles gets the idea that a complete self-engulfing requires that he capture the camera as well in his picture, but that requires a mirror and then that is included in the system and will have to be included in the pictures as well, which would require yet another mirror, etc ad infinitum. This reminds us of Chapter XV, ``Jumping out of the System'' and furthers the point that you really cannot jump out of the system, that study of the system has to be done from within the system.

After thinking about this for a while Achilles needs a wee lie down and the dialogue ends with his imminent reverse peristalsis. (I would feel sick too, after all that pipe smoke.)

Cross-references

The copper, silver, gold triad turns up in the copper lining of the Crab's pipe (p. 481), the silver lining to his problems (p. 486) and the gold lining on his paintings (p. 494).

As always the characters in the dialogues in Copper, Silver, Gold are ``exceedingly droll'' (p. 485).

In Contracrostipunctus the Tortoise tries to slip in a recordgif ``I Cannot Be Played on Record Player X'' in the Crab's phonograph and Achilles doubts he will manage that. The following dialogue ensues (p. 78):

Tortoise:
Curious that you should think so... I don't suppose that you know Gödel's Incompleteness Theorem backwards and forwards, do you?
Achilles:
Know whose Theorem backwards and forwards? I've never heard of anything that sounds like that. I'm sure it's fascinating, but I'd rather hear more about ``music to break records by''. It's an amusing little story. Actually, I guess I can fill in the end. Obviously, there was no point in going on, and so you sheepishly admitted defeat, and that was that. Isn't that exactly it?

Now that the Tortoise instead tries to slip in a record ``I Can Be Played on Record Player X'' a complementary repartee takes place (p. 488):

Crab:
Curious that you should think so... I don't suppose that you know Henkin's Theorem forwards and backwards, do you?
Achilles:
Know whose Theorem forwards and backwards? I've never heard of anything that sounds like that. I'm sure it's fascinating, but I'd rather hear more about ``music to infiltrate phonographs by''. It's an amusing little story. Actually, I guess I can fill in the end. Obviously, Mr. T will find out that there is no point in going on, and so he will sheepishly admit defeat, and that will be that. Isn't that exactly it?

Actually, it is quite curious that the Crab should believe himself to be able to outwit the Tortoise if he actually does know Henkin's theorem forwards and backwards, but since the Tortoise isn't there (in the Dialogue) to deliver the line, the Crab has to do it. (Henkin sentences are explained on p. 541ff.)

Self-Ref and Self-Rep

Hofstadter starts out the chapter by claiming that achieving self-reference by such means as ``This sentence...'' requires a great deal of understanding of English, whereas quining is a more explicit and more readily understood construction.

He then goes on to discuss how to construct a self-reproducing program. This is very dependent on how the language used is constructed, a programming language that explicitly supports self-reproduction would of course allow for very simple self-reproducing programs, but this, just as ``This sentence...'' offloads too much of the problem on the processing unit and hides the interesting parts of the self-reproduction mechanism.

Therefore, a properly self-reproducing entity should actually contain the instructions for its own self-reproduction, ``to the maximum extent possible'', which may or may not be well-defined.

The question is then, what is to be considered a copy of an original? Some variations are suggested, such as a program copying itself backwards or translating itself into another language (the former may of course be considered to be a special case of the latter). The latter in particular has relevance when we are talking about Gödel-numbering, as in the string G, which uses its own Gödel-translation into a number to talk about itself.

Self-reproduction by living organisms is yet another variant of non-literal copying, in that the offspring is not a perfect copy of its parent(s). Hofstadter uses the term ``coarse-grained isomorphism'' to describe the relation between offspring and ancestors, that the family resemblance is the invariant. This I think glosses over several non-trivial points about the Biological Species Concept and the evolution of the genome, as object-oriented inheritance really is not the same as genetic inheritance, but we'll let it stand for the nonce.

Another question is, if we make a copy of an original, what was the original, was it merely the text that got copied, or the text and the environment that copied it?

Now is introduced Typogenetics, a simple model of molecular genetics on the level of DNA replication, ignoring questions about low-level chemistry and the high-level bio logical phenomena.

The typogenetical alphabet consists of only four characters, A, C, G and T. They are called bases and their positions, in the strings they build up, units. These strings, or strands, can be operated on by enzymes which are packets of basic operations known as amino acids. Every enzyme will always start on a given character, so there will be four groups of enzymes. Furthermore, A and G are called purines and C and T pyrimidines. Purines and pyrimidines are complementary so that copy operations will copy As as Ts and Gs as Cs and vice versa.

The enzymes are actually created by ribosomes first crawling along the strand and creating the enzymes that are then let loose to operate on the strand. Unfortunately the description of Typogenetics is somewhat ambiguous, but some reasonable assumptions can be made: searching amino acids (lpu, rpu, lpy, rpy) will run off the end of the strand if they do not find the base they are looking for; only one enzyme at a time will be active, but that all enzymes will have a go, in no determined order, but only once, after which they will disappear; a one-amino-acid enzyme will attach to an A.

The strand is divided into pairs of bases, duplets, and each pair will define an amino acid. The sequence of amino acids is known as the primary structure of an enzyme. It also has a tertiary structure which is its configuration in 2D space---each amino acid will define for the position of the next amino acid in the sequence whether it will be aligned with the current amino acid or to the left or to the right of it. (We may wonder where the secondary structure ended up---for real enzymes it is of some importance, but it has been ignored in Typogenetics due to the simplified model, where the secondary structure does not fit in well---but we will hear of the secondary structure later in the chapter.) It now turns out that the tertiary structure, or rather, the orientation of the last two relative to the first two amino acids determines the binding preferences of the enzyme, i e whether it will start operating on an A, C, G or T.

The AA pair does not code for any particular operation, but instead is a separator between different genes in a strand, so that many different enzymes can be coded for by a single strand.

Hofstadter then suggests that we attempt to define a self-replicating typogenetic strand. It took me a while, but it is actually possible. The self-replicating strand I found is CG TT TT TT TG. Here is how the replication proceeds:

  1. CG TT TT TT TG (let's call it S0) is transcribed into the enzyme cop--lpu--lpu--lpu--lpy (call it e0). This enzyme folds left + left + left, with the result that the last segment is folded to the right relative to the first and therefore this enzyme will bind to a G.
  2. There are two alternative attachment points for the enzyme, the second base or the tenth base (call them S01 and S09, respectively). If it attaches to S01, the following happens:
    1. The enzyme turns on copying and attaches a C opposite the G. Next the enzyme moves left looking for a purine while still copying. As no further purines are present to the left of the G, the enzyme ceases operations and the second strand, consisting of CG, (call this S1) is released.

    2. S1 is transcribed, which results in an enzyme cop (e1). S0 is also transcribed, resulting in a new e0.
    3. e1 would attach to an A, but since there is none, it is thrown away and has no effect on anything. The e0 may either attach to S01 as before, in which case it will generate further copies of S1, or it may attach to S11, which happens to have the same result. It may also attach to S09, which has different results.
    If e0 attaches to S09, the following happens:
    1. The enzyme turns on copying and attaches a C opposite the G. Next the enzyme moves left looking for a purine while still copying and will find S01. Then the enzyme will move further left looking for a new purine, and as there is none, the enzyme will fall off the end of the strand and cease operations, after having made the complement of S0. This complement is CA AA AA AA CG (S2).
    2. S2 is transcribed and results in two enzymes, mvr (e20) and cop (e21). Both will attach to As. S0 (and any S1s) will also be transcribed.
    3. e20 can attach to any of the As in S2, where it will move one base to the right and then cease operations. This changes nothing.
    4. e1 and e21, which are identical, may also attach to any of the As in S2, where they will cause a T to be attached opposite to that A and then cease operations. The T will be set loose, and as it cannot be transcribed, nothing will come from it.
    5. e0 may either attach to S0, as before, in which case we know what will happen, or it may attach to S29. In this case it turns on copying, attaching a C opposite the G. It then moves left looking for a purine while copying and finds S27. It then moves further left looking for a purine and finds S26. It then moves further left looking for a pyrimidine, finds S20 and ceases operations. It now has created the complement of S2, which is CG TT TT TT TG. As this is the same as S0, and S0 still is intact, we now have two copies of S0, which thus has replicated. The cycle may start over again.

An interesting question now is whether this in fact is the shortest possible self-reproducing string. Definitely it gives us a very low upper bound on the shortest replicator and it seems not entirely infeasible to (write a program to) try all 410 = 1048576 strands shorter or equal to ten bases to see if they can replicate. Furthermore, we might be interested in finding a strand which will only need one transcription cycle in order to replicate, rather than the two of S0, but for this we do not have any upper bounds (yet). We might also wonder whether it actually is necessary to create an exact copy of the original strand in order to have self-replication: several different strands may be ``functionally'' equivalent in some sense and we may not bother which of the strands in this equivalence class we actually have at the end of the replication---we could indeed say that if we have strands that can generate new strands that in turn can create new strands, we have replication, regardless of the actual likeness of the daughter strands to the parent strand. We must of course insist that the daughtern strands always can create new strands themselves---it doesn't count if only the parent strand churns out new strands.

There have been attempts to use these kinds of molecules to do actual computations [Adleman, 1994], and while these definitely are interesting it is not obvious that there is a practical way to have molecular computers. In particular exponential problems still grow exponentially, parallelism just delays the point where one has to give up [Hartmanis, 1995].

Then is defined the Central Dogma of Typogenetics, which shows that neither strands nor enzymes can be considered to be only data or programs, but that they change places in a Strange Loop. (Hands drawing each other...) This is in contrast to the MIU-system, TNT and other formal systems, where the wffs cannot modify the inference rules in any way. But, claims Hofstadter, TNT still can talk about itself, through Gödel numbering.

We now go on to look at real DNA and how it behaves. The typogenetic A, C, G and T are matched by adenine, cytosine, guanine and thymine. The pyrimidine/purine distinction is one of their chemical structure and the reason the two types are complementary is that DNA is a double strand in which the bases form the connections between the two halves; a purine and its corresponding a pyrimidine is the same width as the other purine and its pyrimidine. The parts of DNA that are not bases are a standard unit of deoxy phosphate groups and ribose sugars. Together with one base, this unit is known as a nucleotide. Nucleotides bind strongly to each other, the bases do not bind quite as strongly to each other, therefore the DNA can be ``unzipped''. This is necessary both for transcription (decoding) and for replication, when two new DNA strands are created, using the original as template.

Figure 93 shows the standard image of a coiled DNA ``double helix''. One should point out that DNA actually coils in several ways simultaneously, much as a piece of string that is continuously twined in one direction. In the end, the DNA is coiled so thickly that it can be seen in a microscope as a ``chromosome''. DNA is usually coiled completely only during cell division, when it has to be carefully ordered so nothing will break off when the chromosomes are divided among the daughter cells (this of course occasionally happens anyway, with sometimes dire consequences), but for transcription, the relevant part has to be uncoiled [Grunstein, 1992].

Hofstadter goes on to explain how the DNA is situated in the walled-off nucleus of the cell and messages have to be transferred to the organelles outside the nucleus that actually create the proteins coded for by the DNA. (This is really neglecting the majority of the Earth's inhabitants, the prokaryotes---bacteria, archaebacteria, cyanobacteria, et al---that do not have nucleated cells.)

Enzymes are special proteins that catalyse the many reactions that a living organism depends on and normally don't occur at the measly temperature of 310 K, over which, on the other hand, most organic compounds are denatured and/or degraded (broken apart without hope of spontaneous self-assembly).

Now enter RNA. RNA reminds a lot of DNA, but is single stranded and replaces thymine with uracil, another pyrimidine. (There are reasons to suspect that DNA has evolved from RNA, in particular since RNA can operate on itself---one end of the very flexible single strand can cut and splice at the other end.)

Transcription is a fairly complex process that involves many cooperating and counterbalanced functions, but the end result is that an enzyme known as RNA polymerase starts to move along a gene, unzipping the DNA and making an RNA copy of one half of it (it is deterministic which half, as the DNA strand has a direction). Indeed, several RNA polymerase enzymes may be transcribing the same gene, one hot on the heels of another. The RNA copy is called messenger RNA, or mRNA for short. When the gene runs to an end the mRNA is taken out of the nucleus and brought to a ribosome (which among other things contains ribosomal RNA, rRNA). Actually, since we are talking eukaryotes, all introns (non-coding, ``junk'' parts) are first edited out of the mRNA. The ribosome moves along the mRNA by groups of three bases (the original triplet in the DNA is called a codon, we will call the mRNA triplet a codon as well). For each codon there is a particular transfer RNA, tRNA, that will match that and only that (well, chemistry is a random process, but this is a very, very skewed distribution) codon. This tRNA will bring with it an amino acid which is specific for it. (There are 43 = 64 different ways to combine the four bases to make codons, but they only code for twenty amino acids---the last base in a codon is usually redundant.) This amino acid will be picked up by the ribosome, the tRNA is released and goes out to look for a new amino acid, the ribosome moves along to the next codon and a new tRNA with an amino acid comes along, this amino acid is joined to the previous one and the process is then repeated until the mRNA strand is exhausted. Often several ribosomes may be active on the same mRNA, in pipeline fashion. All this sounds so purposeful, some become religious on account of it, but we shall consider that to be chickening out.

The amino acid chain built up in this way is then released from the ribosome and starts folding in on itself to form a protein. The primary structure is, as we recall, the order of the amino acids. The secondary structure is the buildup of a number of basic motifs, the alpha helix, beta sheet, random coil and others, these are then folded further together to form the tertiary structure. The quaternary structure is the connections of multiple peptide chains building up a protein.

How this folding takes place is a matter of much concern for molecular biologists. While much still is computationally intractable, advances have been made since GEB:EGB was written [Kinoshita, 1990]. Primary mechanisms are the affinity of the amino acids for water, so that water-hating amino acids will end up on the inside of the protein and water-loving on the outside, but there are of course other parameters, such as hydrogen and sulphur bonds. Also, this final structure need not be uniquely determined, which has consequences, as we shall see later.

A folded protein now has various properties on account of its folded, three-dimensional structure, such as elasticity or rigidity for structural proteins or grooves suitable for catching other molecules to modify for catalytic proteins, enzymes. Hofstadter cautions us not to fall for the holistic heresy just because the function of a protein cannot be determined as a context-free function of each individual amino acid, as in Typogenetics.

While we are not as yet able to tell, by just determining the codon sequence in a gene, whether a person will have the potential (remember the difference between genotype and phenotype) to become e g a talented musician, there is much work that finds correlations between genes and their expressions. So we could imagine a future in which we can, by studying the genome of an individual, tell what she probably looks like or whether she could be a good musician, still without knowing how the genes give rise to these traits.

While tRNA, ribosomes and the rest are certainly the results of transcription from DNA, it cannot bootstrap itself entirely on its own, the transcription apparatus must already be there from the start. Those who didn't become religious earlier, usually do so now, but we will persist in seeing this as an ongoing, continually modified tradition from the first, very much simpler self-replicating systems that somehow arose spontaneously. (The twenty amino acids used by Earth organisms are also the simplest amino acids, and a number of them have been observed in space, so they at least can arise spontaneously, and as the Miller-Urey experiments in the 50s showed, can polymerise under fairly simple conditions.)

We note in passing also notes that transcription does not have to be unique, the previously mentioned virus φX174 manages to code for two different proteins in the same piece of DNA by shifting the reading frame one unit.gif Hofstadter notes that this is an amazing amount of data compression.gif

DNA of course has to have the ability to replicate itself, which it can do with the help of enzymes that unzip the double strand and add complementary nucleotides to the resulting single strands to build new double strands. Separation into single strands can even be done by gentle heating [Mullis, 1990].

Hofstadter then makes an elaborate analogy between Molecular Biology and Mathematical Logic in which it turns out that the Genetic Code was the model for the Gödel Code used in Chapter IX.

Then we get a mapping between the Contracrostipunctus and Molecular Biology, in which it is claimed that one always can create a strand of DNA, which, when injected into a suitable cell, will cause the destruction of this cell. DNA of this kind is in nature supplied by viri. (Though Hofstadter, to make the analogy with the Tortoise's malignant records more complete, makes the additional proviso that the injected DNA be rendered inoperative by the destruction of the cell, something that real viri of course would not benefit from.)

Viri operate by injecting genetic material into a host cell. This host cell will then express this foreign DNA, creating new viri in such huge quantities that the cell finally bursts and spews out the viri, which can then go forth and infect new cells. I choose the term ``genetic material'' rather than ``DNA'' for indeed not all viri do carry and inject DNA. Retroviri instead carry RNA (which presumably, while being more sensitive to breaks and errors in transcription, takes less space), which is then converted into DNA by an enzyme called reverse transcriptase. This contradicts the .DOGMA I that says that information flows from DNA to RNA to proteins, and caused some amount of upset at the time.gif We note that bacteria can label their DNA and thus recognise foreign DNA, at least until the viri also learn to label their DNA the same way.

As we said, while being a counterpart of Gödel strings, self-destroying viri are not viable, but real viri do replicate themselves in host cells, and indeed there is a mathematical counterpart to these as well. These are the Henkin sentences, which are in essence the negation of Gödel sentences, in that they assert that they can be proven in TNT. Henkin sentences may just assert that there is a derivation of them in TNT, in which case they are called implicit, or they may contain their own derivation, in which case they are explicit sentences. Explicit sentences obviously need not be theorems.

This has a counterpart in the realm of viri: self-assembling viri only code for their component parts and these will then find each other and make up new viri. In these they can be likened to implicit Henkin sentences. Other viri need to code for the enzymes that will direct their assembly, these are then like explicit Henkin sequences.

The discussion about repressors and inducers can be profitably enhanced by reading [Tjian, 1995]. We just note that transcription of a gene starts from something called a TATA box. The Dynamic Duo strikes again!

Cross-references

The DNA strands on p. 505 are of course not arbitrary, the GGGG is Achilles' organ point in ``... Ant Fugue'' (p. 330), the ATTACCA is the Attacca hidden in the ``Prelude, Ant Fugue'' (pp. 284 & 311) as well as in the φX174 virus (p. 176), and the CATCATCATCAT is purportedly part of the cat genome (p. 532).

The DNA hemiolia on p. 519, brings out the copper, silver, gold triad from the aspartic acid and leucine codons which also are shown in figure 96. CUA and GAU are unfortunately only almost complementary, as one of them would have to be read backwards.

The Magnificrab, Indeed

In the Dialogue, the Tortoise and the Crab seem to be out to pull Achilles leg out of its socket. The Crab tells about a letter he had gotten from an Indian mathematician by the name of Najunamar (Ramanujan backwards for the truly dense) who has proved many very peculiar (and trivial) mathematical problems. The Crab takes this as proof of the mystical insight given to Orientals, but the Tortoise is more skeptical.

The Crab takes out his flute and plays. To Achilles his note sheets look like TNT statements, and indeed, the Crab's appreciation of music seems to be directly coupled to whether the TNT statements are theorems or not. In particular he likes the melody that corresponds to the statement ``13 is prime'' (p. 553). When Achilles modifies it to ``14 is prime'' (p. 554), the Crab is very displeased and neither does he like the tune ``17 is not prime'' (ibid.). ``32 + 42 = 52'' (p. 553) is acceptable, as is ``b2 = 2a2 only if a is 0''. The long tune ``50 is the smallest number that can be written as a sum of two squares in two different ways'' (p. 557) is also acceptable. Achilles, having tested the Crab's ability in these ways, then attempts to prove the Goldbach Conjecture (p. 557), but the Crab excuses himself and will not take up the offer.

It seems as if Achilles catches on to the other two putting him on as he notes that ``this'' (which could be interpreted as the hill they are on) is a bluff and that he will have to remember that. He also says something about a ``prime teas[e]''. Still he expresses his admiration for the Crab, so the brave man apparently holds no grudge against him.gif

Cross-references

The story of the Crab telling Truths from Non-truths by their Beauty recalls John Keats' ``Ode on a Grecian Urn'':

``Beauty is Truth, Truth Beauty''---that is all
Ye know on Earth and all Ye need to know.

There are a number of references made to Srinivasa Ramanujangif in the dialogue. 1729 (p. 551) is the well-known Ramanujan number that is the smallest number that can be written as a sum of two cubes in two different ways, and which happened to be number of the cab G. H. Hardy had taken to Ramanujan's home one day. Finding the smallest number expressible as the sum of two squares in two different ways (p. 557) is of course simpler. On Hardy's question about the corresponding number for fourth powers, Ramanujan conjectured that it would be ``very large'' (p. 564). Also, the Crab's reason for disbelieving Najunamar is the opposite of Hardy's reason to believe Ramanujan (p. 563). However, I do not think Ramanujan had anything to do with any attempts to prove the Four-Colour Theorem. (Note that the index refers to p. 550 for ``Four-color Theorem, parodied'', rather than p. 551, where it occurs in my book. (P. 550 is taken up by an Escher picture.) The ``Goldbach Conjecture, parodied'' and ``Fermat's Last Theorem, parodied'' are attributed to the correct page.

The Crab's statement that ``... two tildes in a row never fails to give a gay little twist'' (p. 554) seems an echo of Hofstadter's claim ``... nature seems to love double-negations'' (p. 545).

Church, Turing, Tarski and Others

Chapter XVII (or rather, Douglas Hofstadter) is concerned with showing how brains and computer programs are ``isomorphic'' to each other on a sufficiently high level. As a stepping stone for this we are introduced to the Church-Turing Thesis. This thesis (which is not a proven Theorem, but a conjecture on the part of Church, Turing and others) says that for any kind of mathematical problem that humans know how to solve there will be a recursive function that can do the same.

Srinivasa Ramanujan and ``idiots savants'', that seemingly can perform mathematical miracles without rec[o]ursing to the plodding algorithms most of us use, are set up as straw men. Hofstadter blithely assumes that these math wizards in fact use the same algorithms as the rest of us (or possibly optimised variants of them) but execute them very, very fast. The arguments for this are that Ramanujan often was wrong in his theories and that ``lightning calculators'' indeed perform slower the larger the numbers they have to manipulate get. We will accept the conclusion for the time being.

A bolder version of the CT Thesis then says that not only can humans and machines utilise algorithms that give the same results, but that these algorithms in fact are the same---not meaning that humans necessarily employ the same standard algorithms as computers, but that the algorithms used by humans can be translated into isomorphic recursive functions.

Now, most of us can accept that this may be true for doing mathematics, but what about daily life? As noted in the beginning of the chapter, an intelligent being not only has to be able to make deductions about the state of the world, but also have a feeling for what deductions are sensible/useful to make in this infinitely complex universe we live in.

In mathematics one can take a very high-level view of what is going on, but in real life (as in molecular genetics), the levels are tangled together, in particular the creative human qualities of reasoning by analogy and imagery. So, if we are to make a recursive function that simulates a brain we cannot just take the highest-level processes and simulate them, as they are interdependent on lower level processes but have to simulate lower levels as well, possibly all the way down to the ``hardware'' (neurons). This sounds a lot like what connectionists are doing today, and indeed Hofstadter follows up by noting that having a neural network does not necessarily imply that higher-level meaning automatically appears.

Also, if we are to simulate neurons, we have to ascertain that everything that goes on in them is indeed computable by a recursive function, which is stated by yet another reformulation of the CT Thesis. While this may seem obvious, there are indeed thinkers, such as Roger Penrose, that claim that minds depend on magical quantum mechanical phenomena that cannot be reproduced by computation [Penrose, 1989]. Still, Hofstadter hopes that AI will not require simulation of neural networks. I haven't read his latest book, so I do not know if he still holds on to this in spite of the spectacular success of artificial neural networks, subsumption architectures and other ``low-level'' approaches to intelligent systems [Minsky, 1994,Wallich, 1991].

Then we go on to questions of Truth and Beauty. ``Soulists'' believe that humans, or any living organisms for that matter, have some characteristic(s) that set them apart from non-living matter. (When we look at prions, viri and synthetic self-replicating molecules [Rebek, Jr., 1994] the question of what exactly separates living from non-living matter rears its ugly head. We will stick ours in the sand.) Nowadays I think the polite term is not ``soul'', but ``consciousness'' [Horgan, 1994,Searle, 1990], but it seems to boil down to much the same concept. If minds indeed are different from machines then it is of course possible that they could perform such feats of Truth-recognition as the Crab purported to do in the Dialogue, even though they are forbidden for machines by Church's Theorem. Furthermore, concepts such as Beauty may then be unique for minds and inaccessible to mere computers. This does not necessarily mean that there will be a single, concept of Beauty that all minds or souls will agree on, since minds presumably can have their own ideas about what they do and do not like.

The Theodore Roszak who is mentioned in the text is a professor of history at Cal State Hayward. He is best known for his 1969 book The Making of a Counter Culture. In it, he criticized the ``objective'' way of viewing the world, and the scientific way of explanation that involves a sharp separation between objective and subjective knowledge. He seems to have objected not to science itself, but with the 20th century view that seeing the world through science is the only way of looking at it.gif

So, if rational behaviour can be programmed on computers, what about the thoroughly irrational behaviour humans often engage in? There is of course a fundamental question of whether people ever engage in irrational behaviour at all, it seems to be much a matter of definition, but in anyway, there is absolutely nothing that keeps perfectly rational and reliable processes from giving irrational results. We know these phenomena as bugs.

Hofstadter takes yet a few swings at J. R. Lucas for having confused levels of AI programs and says that the hardware level is the only one that by necessity will be a formal logical system, whereas the higher levels, those which represent actual thoughts and beliefs, do not have to implement e g propositional logic.

Church's Theorem says that there is no recursive function that can determine whether a given string of TNT is a theorem in TNT. Tarski's Theorem says that there is non-recursive function that can determine the truth of a given TNT string either. Assuming that the CT Thesis is true, it then follows that humans cannot do these either, and that presumably goes for Crabs as well. The question is then, as someone pointed out, that if we were to find a Truth by other means than a recursive function, how would we demonstrate the validity of our claim to anyone else? It seems that the only means we (as scientists in the Westernised world, at least) agree upon as conveying Truth try to be as close to recursive functions as possible, as we consider these explanations to be simple enough to trust.

But then, assuming we have determined a truth, or a falsity, we cannot consciously believe that that and its negation are valid at the same time. Hofstadter suggests that perhaps conflicting truth values, such as in the Epimenides sentence, attempt to set up patterns in the brain that physically cannot be active at the same time.

Cross-references

I wonder in my mind if the CT Thesis has anything to do with the Crab and Tortoise pulling Achilles' leg.

It is an interesting coincidence that Roger Penrose, who is mentioned as the inventor of the illusion of the eternally ascending/descending staircase in the Introduction (p. 15) has become one of Hofstadter's opponents in the AI debate.

References

Adleman, 1994
Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266:1021--1024.

Barnsley and Hurd, 1993
Barnsley, M. F. and Hurd, L. P. (1993). Fractal image compression. Peters, Wellesley, MA.

Grunstein, 1992
Grunstein, M. (1992). Histones as regulators of genes. Scientific American, pages 40--47.

Hartmanis, 1995
Hartmanis, J. (1995). On the weight of computations. Bulletin EATCS.

Horgan, 1994
Horgan, J. (1994). Can science explain consciousness? Scientific American, pages 72--78.

Kinoshita, 1990
Kinoshita, J. (1990). Net result: Folded protein. Scientific American, pages 12--13.

Minsky, 1994
Minsky, M. (1994). Will robots inherit the earth? Scientific American, pages 87--91.

Mullis, 1990
Mullis, K. B. (1990). The unusual origin of the polymerase chain reaction. Scientific American, pages 36--43.

Penrose, 1989
Penrose, R. (1989). The Emperor's New Mind. Oxford University Press, Oxford.

Prusiner, 1984
Prusiner, S. B. (1984). Prions. Scientific American.

Prusiner, 1995
Prusiner, S. B. (1995). The prion diseases. Scientific American, pages 30--37.

Raymond, 1991
Raymond, E. S., editor (1991). The New Hacker's Dictionary. MIT Press.

Rebek, Jr., 1994
Rebek, Jr., J. (1994). Synthetic self-replicating molecules. Scientific American, pages 34--40.

Searle, 1990
Searle, J. R. (1990). Is the brain's mind a computer program? Scientific American, pages 20--25.

Tjian, 1995
Tjian, R. (1995). Molecular machines that control genes. Scientific American, pages 38--45.

Wallich, 1991
Wallich, P. (1991). Silicon babies. Scientific American, pages 82--91.
...pipe.
This hints at the old paradox that one is allowed to pray while smoking, but not smoke while praying, something occasionally quoted as a proof that human thoughts map imperfectly onto formal logic, though it probably more indicates the necessity for accounting for temporal relations when describing the real world. (The point of the one-sided interdiction is of course that one is allowed to pray should one's mind turn to Matters Unworldly while smoking, like it did for Bach, but one should not be so unconcentrated while praying that one starts smoking.)

...Achilles.
We note in passing that it is quite common for limericks to be self-referential or make meta-jokes, as in

There was a young man from Japan
whose verses never would scan.
He said ``Yes, I know
this is really so
because I always try to get as many words into the last line as I possibly can!''

...record
This reminds me of the guy who tried to slip out of a record store with a CD hidden in his trousers. A hawk-eyed shop assistant noted this and politely asked:
``Excuse me sir, is that a record in your trousers?''
``Well, it may not be a record, but I'm mighty proud of it!''

...unit.
Someone wanted to write a program that could be interpreted in this way. I refer to Mel's blackjack program, as described in [Raymond, 1991] as an example of how this has been done.

...compression.
The question was put as to how a human could be represented by the presumably very small amount of data in the human genome. We could compare this with the Iterated Functions System [Barnsley and Hurd, 1993] for image compression, in which an image is stored as a small number of generating functions, which can then be executed to generate the image with arbitrary precision.

...time.
Further upset was caused when prions were found [Prusiner, 1984]. This infectious agent is too small to contain any genetic material and thus has to be protein only, but a self-replicating protein is forbidden according to .DOGMA I. The current theory [Prusiner, 1995] is that prions are proteins with an alternative, though less probable, harmful structure, that can induce other proteins of the same kind to assume the alternate structure---the remains of .DOGMA I are saved.

...him.
For those feeling less magnanimous and Mock Turtle soup having been mentioned before, here is a recipe for Devil Crab: Chop a shallot and 8--10 chive stems. Fry the shallot in 30 ml butter, add 200 g of crab meat, 5--10 ml French mustard and 5 ml Worcestershire sauce. Let stew on low heat. Add 300 ml Béchamel sauce and the chives. Season with salt and cayenne pepper to taste. Take the stew off the stove and thicken with two egg yolks. Fill dishes with the stew, sprinkle with bread crumbs and butter pats. Bake in oven in 600 K for 180--300 s.

...Ramanujan
Ramanujan, like many other great mathematicians and achievers, died young. There are on the other hand many great mathematicians and achievers that lived to old age. I dare not say whether it is dangerous to be a genius without access to more complete statistics.

...it.
Thanks to Rene Mandel for the library lookup.



Kai-Mikael Jää-Aro
Tue Feb 6 16:26:27 MET 1996