Complexity - A Guided Tour Part 4

A simple example will make all this clearer. To make things really simple, a.s.sume that (like a real computer) the only possible symbols that can be on a tape are 0, 1, and a blank symbol indicating a blank tape cell. Let's design a Turing Machine that reads a tape containing all blank cells except for some number of 1s sandwiched between exactly two 0s (e.g., 011110) and determines whether the number of Is is even or odd. If even, then the final output of the machine will be a single 0 (and all other cells blank) on the tape. If odd, the final output will be a single 1 (and all other cells blank). a.s.sume the input always has exactly two 0s on the tape, with zero or more 1s between them, and all blanks on either side of them.

Our Turing machine's head will have four possible states: start, even, odd, and halt. The head will start on the left-most 0 and in the start state. We will write rules that cause the head to move to the right, one cell at a time, replacing the 0s and 1s it encounters with blanks. If the head reads a 1 in the current cell, the head goes into the odd state and moves one cell to the right. If it reads a 1 again it goes into the even state and moves one cell to the right, and so on, switching between the even and odd states as 1s are read.

When the head reads a 0, it has come to the end of the input, and whatever state it is in, odd or even, is the correct one. The machine will then write a corresponding 0 or 1 in its current cell and go into the halt state.

Here are the rules for the tape head that implement this algorithm: If you are in the start state and read a 0, then change to the even state, replace the 0 with a blank (i.e., erase the 0), and move one cell to the right.

If you are in the even state and read a 1, change to the odd state, replace the 1 with a blank, and move one cell to the right.

If you are in the odd state and read a 1, change to the even state, replace the 1 with a blank, and move one cell to the right.

If you are in the odd state and read a 0, replace that 0 with a 1 and change to the halt state.

If you are in the even state and read a 0, replace that 0 with a 0 (i.e., don't change it) and change to the halt state.

The process of starting with input symbols on the tape and letting the Turing machine serially process that input by using such rules is called "running the Turing machine on the input."

Definite Procedures Defined as Turing Machines.

In the example above, a.s.suming that the input is in the correct format of zero or more 1s sandwiched between two 0s, running this Turing machine on the input is guaranteed to produce a correct answer for any input (including the special case of zero 1s, which is considered to be an even number). Even though it seems kind of clunky, you have to admit that this process is a "definite procedure"-a precise set of steps-for solving the even/odd problem. Turing's first goal was to make very concrete this notion of definite procedure. The idea is that, given a particular problem to solve, you can construct a definite procedure for solving it by designing a Turing machine that solves it. Turing machines were put forth as the definition of "definite procedure," hitherto a vague and ill-defined notion.

When formulating these ideas, Turing didn't build any actual machines (though he built significant ones later on). Instead, all his thinking about Turing machines was done with pencil and paper alone.

Universal Turing Machines.

Next, Turing proved an amazing fact about Turing machines: one can design a special universal Turing machine (let's call it U) that can emulate the workings of any other Turing machine. For U to emulate a Turing machine M running on an input I, U starts with part of its tape containing a sequence of 0s, 1s, and blanks that encodes input I, and part of its tape containing a sequence of 0s, 1s, and blanks that encodes machine M. The concept of encoding a machine M might not be familiar to you, but it is not hard. First, we recognize that all rules (like the five given in the "simple example" above) can be written in a shorthand that looks like -Current State-Current Symbol-New State-New Symbol-Motion-.

In this shorthand, Rule 1 above would be written as: -start-0-even-blank-right-.

(The separator '-' is not actually needed, but makes the rule easier for us to read.) Now to encode a rule, we simply a.s.sign different three-digit binary numbers to each of the possible states: for example, start = 000, even = 001, odd = 010, and halt = 100. Similarly, we can a.s.sign three-digit binary numbers to each of the possible symbols: for example, symbol '0' = 000, symbol '1' = 001, and symbol blank = 100. Any such binary numbers will do, as long as each one represents only one symbol, and we are consistent in using them. It's okay that the same binary number is used for, say, start and '0'; since we know the structure of the rule shorthand above, we will be able to tell what is being encoded from the context.

Similarly, we could encode "move right" by 000, and "move left" by 111. Finally, we could encode the '-' separator symbol above as 111. Then we could, for example, encode Rule 1 as the string 111000111000111001111100111000111.

which just subst.i.tutes our codes for the states and symbols in the shorthand above. The other rules would also be encoded in this way. Put the encoding strings all together, one after another, to form a single, long string, called the code of Turing machine M. To have U emulate M running on input I, U's initial tape contains both input I and M's code. At each step U reads the current symbol in I from the input part of the tape, decodes the appropriate rule from the M part of the tape, and carries it out on the input part, all the while keeping track (on some other part of its tape) of what state M would be in if M were actually running on the given input.

When M would have reached the halt state, U also halts, with the input (now output) part of its tape now containing the symbols M would have on its tape after it was run on the given input I. Thus we can say that "U runs M on I." I am leaving out the actual states and rules of U, since they are pretty complicated, but I a.s.sure you that such a Turing machine can be designed. Moreover, what U does is precisely what a modern programmable computer does: it takes a program M that is stored in one part of memory, and runs it on an input I that is stored in another part of memory. It is notable that the first programmable computers were developed only ten years or so after Turing proved the existence of a universal Turing machine.

Turing's Solution to the Entscheidungsproblem.

Recall the question of the Entscheidungsproblem: Is there always a definite procedure that can decide whether or not a statement is true?

It was the existence of a universal Turing machine that enabled Turing to prove that the answer is "no." He realized that the input I to a Turing machine M could be the code of another Turing machine. This is equivalent to the input of a computer program being the lines of another computer program. For example, you might write a program using a word processor such as Microsoft Word, save it to a file, and then run the "Word Count" program on the file. Here, your program is an input to another program (Word Count), and the output is the number of words in your program. The Word Count program doesn't run your program; it simply counts the words in it as it would for any file of text.

a.n.a.logously, you could, without too much difficulty, design a Turing machine M that counted the 1s in its input, and then run M on the code for a second Turing machine M'. M would simply count the 1s in M''s code. Of course, the Universal Turing Machine U could have the code for M in the "program" part of its tape, have the code for M' in the "input" part of its tape, and run M on M'. Just to be perverse, we could put the code for M in both the "program" and "input" parts of U's tape, and have M run on its own code! This would be like having the Word Count program run on its own lines of code, counting the number of words it contains itself. No problem!

All this may seem fairly pedestrian to your computer-sophisticated mind, but at the time Turing was developing his proof, his essential insight-that the very same string of 0s and 1s on a tape could be interpreted as either a program or as input to another program-was truly novel.

Now we're ready to outline Turing's proof.

Turing proved that the answer to the Entscheidungsproblem is "no" by using a mathematical technique called "proof by contradiction." In this technique, you first a.s.sume that the answer is "yes" and use further reasoning to show that this a.s.sumption leads to a contradiction, and so cannot be the case.

Turing first a.s.sumed that the answer is "yes," that is, there is always a definite procedure that can decide whether or not a given statement is true. Turing then proposed the following statement: Turing Statement: Turing machine M, given input I, will reach the halt state after a finite number of time steps.

By the first a.s.sumption, there is some definite procedure that, given M and I as input, will decide whether or not this particular statement is true. Turing's proof shows that this a.s.sumption leads to a contradiction.

It is important to note that there are some Turing machines that never reach the halt state. For instance, consider a Turing machine similar to the one in our example above but with only two rules: If you are in the start state and read a 0 or a 1, change to the even state and move one cell to the right.

If you are in the even state and read a 0 or a 1, change to the start state and move one cell to the left.

This is a perfectly valid Turing machine, but it is one that will never halt. In modern language we would describe its action as an "infinite loop"-behavior that is usually the result of a programming bug. Infinite loops don't have to be so obvious; in fact, there are many very subtle ways to create an infinite loop, whose presence is then very hard to detect.

Our a.s.sumption that there is a definite procedure that will decide the Turing Statement is equivalent to saying that we can design a Turing machine that is an infinite loop detector.

More specifically, our a.s.sumption says that we can design a Turing machine H that, given the code for any machine M and any input I on its tape, will, in finite time, answer "yes" if M would halt on input I, and "no" if M would go into an infinite loop and never halt.

The problem of designing H is called the "Halting problem." Note that H itself must always halt with either a "yes" or "no" answer. So H can't simply run M on I, since there would be some possibility that M (and thus H) would never halt. H has to do its job in some less straightforward way.

It's not immediately clear how it would work, but nonetheless we have a.s.sumed that our desired H exists. Let's denote H(M, I) as the action of running H on input M and I. The output is "yes" (e.g., a single 1 on the tape) if M would halt on I and "no" (e.g., a single 0 on the tape) if M would not halt on I.

Now, said Turing, we create a modified version of H, called H', that takes as input the code for some Turing machine M, and calculates H(M, M). That is, H' performs the same steps that H would to determine whether M would halt on its own code M. However, make H' different from H in what it does after obtaining a "yes" or a "no". H just halts, with the answer on its tape. H' halts only if the answer is "No, M does not halt on code M." If the answer is "Yes, M does halt on code M," H' goes into an infinite loop and never halts.

Whew, this might be getting a bit confusing. I hope you are following me so far. This is the point in every Theory of Computation course at which students either throw up their hands and say "I can't get my mind around this stuff!" or clap their hands and say "I love this stuff!"

Needless to say, I was the second kind of student, even though I shared the confusion of the first kind of student. Maybe you are the same. So take a deep breath, and let's go on.

Now for Turing's big question: What does H' do when given as input the code for H' , namely, its own code? Does it halt?

At this point, even the second kind of student starts to get a headache. This is really hard to get your head around. But let's try anyway.

First, suppose that H' does not halt on input H'. But then we have a problem. Recall that H', given as input the code for some Turing machine M, goes into an infinite loop if and only if M does halt on M. So H' not halting on input M implies that M does halt on input M. See what's coming? H' not halting on input H' implies that H' does halt on input H'. But H' can't both halt and not halt, so we have a contradiction.

Therefore, our supposition that H' does not halt on H' was wrong, so H' must halt on input H'. But now we have the opposite problem. H' only halts on its input M if M does not halt on M. So H' only halts on H' if H' does not halt on H'. Another contradiction!

These contradictions show that H' can neither halt on input H' nor go into an infinite loop on input H'. An actual machine has to do one or the other, so H' can't exist. Since everything that H' does is allowed for a Turing machine, except possibly running H, we have shown that H itself cannot exist.

Thus-and this is Turing's big result-there can be no definite procedure for solving the Halting problem. The Halting problem is an example that proves that the answer to the Entscheidungsproblem is "no"; not every mathematical statement has a definite procedure that can decide its truth or falsity. With this, Turing put the final nail in the coffin for Hilbert's questions.

Turing's proof of the uncomputability of the Halting problem, sketched above, uses precisely the same core idea as G.o.del's incompleteness proof. G.o.del figured out a way to encode mathematical statements so that they could talk about themselves. Turing figured out a way to encode mathematical statements as Turing machines and thus run on one another.

At this point, I should summarize Turing's momentous accomplishments. First, he rigorously defined the notion of "definite procedure." Second, his definition, in the form of Turing machines, laid the groundwork for the invention of electronic programmable computers. Third, he showed what few people ever expected: there are limits to what can be computed.

The Paths of G.o.del and Turing.

The nineteenth century was a time of belief in infinite possibility in mathematics and science. Hilbert and others believed they were on the verge of realizing Leibniz's dream: discovering an automatic way to prove or disprove any statement, thus showing that there is nothing mathematics could not conquer. Similarly, as we saw in chapter 2, Laplace and others believed that, using Newton's laws, scientists could in principle predict everything in the universe.

In contrast, the discoveries in mathematics and physics of the early to middle twentieth century showed that such infinite possibility did not in fact exist. Just as quantum mechanics and chaos together quashed the hope of perfect prediction, G.o.del's and Turing's results quashed the hope of the unlimited power of mathematics and computing. However, as a direct consequence of his negative answer to the Entscheidungsproblem, Turing set the stage for the next great discovery, electronic programmable computers, which have since changed almost everything about the way science is done and the way our lives are lived.

After publis.h.i.+ng their complementary proofs in the 1930s, Turing and G.o.del took rather different paths, though, like everyone else at that time, their lives were deeply affected by the rise of Hitler and the Third Reich. G.o.del, in spite of suffering from on-and-off mental health problems, continued his work on the foundations of mathematics in Vienna until 1940, when he moved to the United States to avoid serving in the German army. (According to his biographer Hao w.a.n.g, while preparing for American citizens.h.i.+p G.o.del found a logical inconsistency in the U.S. Const.i.tution, and his friend Albert Einstein had to talk him out of discussing it at length during his official citizens.h.i.+p interview.) G.o.del, like Einstein, was made a member of the prestigious Inst.i.tute for Advanced Study in Princeton and continued to make important contributions to mathematical logic. However, in the 1960s and 1970s, his mental health deteriorated further. Toward the end of his life he became seriously paranoid and was convinced that he was being poisoned. As a result, he refused to eat and eventually starved to death.

Turing also visited the Inst.i.tute for Advanced Study and was offered a members.h.i.+p but decided to return to England. During World War II, he became part of a top-secret effort by the British government to break the so-called Enigma cipher that was being used by the German navy to encrypt communications. Using his expertise in logic and statistics, as well as progress in electronic computing, he took the lead in developing code-breaking machines that were eventually able to decrypt almost all Enigma communications. This gave Britain a great advantage in its fight against Germany and arguably was a key factor in the eventual defeat of the n.a.z.is.

After the war, Turing partic.i.p.ated in the development of one of the first programmable electronic computers (stemming from the idea of his universal Turing machine), at Manchester University. His interests returned to questions about how the brain and body "compute," and he studied neurology and physiology, did influential work on the theory of developmental biology, and wrote about the possibility of intelligent computers. However, his personal life presented a problem to the mores of the day: he did not attempt to hide his h.o.m.os.e.xuality. h.o.m.os.e.xuality was illegal in 1950s Britain; Turing was arrested for actively pursuing relations.h.i.+ps with men and was sentenced to drug "therapy" to treat his "condition." He also lost his government security clearance. These events may have contributed to his probable suicide in 1954. Ironically, whereas G.o.del starved himself to avoid being (as he believed) poisoned, Turing died from eating a poisoned (cyanide-laced) apple. He was only 41.

CHAPTER 5.

Evolution.

All great truths begin as blasphemies.

-George Bernard Shaw, Annajanska, The Bolshevik Empress.

THE SECOND LAW OF THERMODYNAMICS states that the total entropy of an isolated system will always increase until it reaches its maximum value. Everyone knows this instinctively-it happens not only in our understanding of science, but also in our daily lives, and is ingrained in humans' conceptions of history and in our art, literature, and religions. The Buddha tells us that "Subject to decay are all compounded things." The Old Testament prophet Isaiah foretells that "The earth shall wax old like a garment." Shakespeare asks, O! how shall summer's honey breath hold out,

Against the wrackful siege of battering days,

When rocks impregnable are not so stout,

Nor gates of steel so strong but Time decays?

It is a gloomy message, this inexorable march toward maximum entropy. But nature gives us a singular counterexample: Life. By anyone's measure, living systems are complex-they exist somewhere in the middle ground between order and disorder. According to our intuitions, over the long history of life, living systems have become vastly more complex and intricate rather than more disordered and entropic.

We know that to decrease entropy, work must be done. Who or what is doing the work of creating and maintaining living systems and making them more complex? Some of the world's religions propose that a deity is responsible, but in the mid-1800s, Charles Darwin proposed that instead, the history of life has resulted from the invisible hand of evolution via natural selection.

No idea in science has been more threatening to humans' conceptions about themselves than Darwin's theory of evolution; it arguably has been the most controversial idea in the history of science. But it is also one of the best ideas. The philosopher Daniel Dennett strongly affirms this: If I were to give an award for the single best idea anyone has ever had, I'd give it to Darwin, ahead of Newton and Einstein and everyone else. In a single stroke, the idea of evolution by natural selection unifies the realm of life, meaning, and purpose with the realm of s.p.a.ce and time, cause and effect, mechanism and physical law.

This chapter sketches the history and main ideas of Darwinian evolution and how it produces organization and adaptation. Concepts from evolutionary theory will come up again and again in the remainder of the book. In chapter 18, I describe how some of these concepts are being radically modified in light of the unexpected results coming out of the molecular revolution in biology and the results of complex systems ideas as applied to evolution.

Pre-Darwinian Notions of Evolution.

The word evolution means "gradual change." Biological evolution is the process of gradual (and sometimes rapid) change in biological forms over the history of life. Until the eighteenth century, the prevailing opinion was that biological forms do not change over time; rather, all organisms were created by a deity and have largely remained in their original form since their creation. Although some ancient Greek and Indian philosophers had proposed that humans arose via trans.m.u.tation from other species, in the West the conception of divine creation began to be widely questioned only in the eighteenth century.

In the mid-1700s, 100 years before Darwin proposed his theory, a French zoologist named George Louis Leclerc de Buffon published a many-volume work ent.i.tled Historie Naturelle, in which he described the similarities between different species. Buffon suggested that the earth is much older than the Biblical 6,000 years and that all modern organisms evolved from a single ancestor, though he did not propose a mechanism for this evolution. Buffon's work in biology and geology was a significant break from the prevailing creationist viewpoint. Not surprising, the Catholic Church in France burned copies of his books.

Charles Darwin's grandfather, Erasmus Darwin, was another prominent eighteenth-century scientist who believed in the evolution of all species from a single ancient ancestor. He proposed mechanisms for evolution that were precursors to his grandson's theory of natural selection. Erasmus Darwin expressed his ideas both in scientific writing and in poetry: Organic life beneath the sh.o.r.eless waves

Was born and nurs'd in ocean's pearly caves;

First forms minute, unseen by spheric gla.s.s,

Move on the mud, or pierce the watery ma.s.s;

These, as successive generations bloom,