Turing's Cathedral: The Origins of the Digital Universe (Penguin Press Science)

by George Dyson

The new technique propagated widely, along with the growing number of computers on which it could run. Refinements were made, especially the so-called Metropolis algorithm (later the Metropolis-Hastings algorithm) that made Monte Carlo even more effective by favoring more probable histories from the start. “The most important property of the algorithm is … that deviations from the canonical distribution die away,” explains Marshall Rosenbluth, who helped invent it. “Hence the computation converges on the right answer! I recall being quite excited when I was able to prove this.”

Monte Carlo opened a new domain in mathematical physics: distinct from classical physics, which considers the precise behavior of a small number of idealized objects, or statistical mechanics, which considers the collective behavior, on average, of a very large number of objects, Monte Carlo considers the individual, probabilistic behavior of an arbitrarily large number of individual objects, and is thus closer than either of the other two methods to the way the physical universe actually works.

With the success of Monte Carlo came a sudden demand for a reliable supply of random numbers; there was a shortage of them. Pseudo-random numbers could be generated within a computer as needed, but as von Neumann warned, “any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

Biological evolution is, in essence, a Monte Carlo search of the fitness landscape, and whatever the next stage in the evolution of evolution turns out to be, computer-assisted Monte Carlo will get there first.

Ulam himself appeared to violate the second law of thermodynamics by performing useful work, with no visible expenditure of energy, simply by opening doors to the right ideas at the right time.

Monte Carlo was the realization, through digital computing, of what Maxwell could only imagine: a way to actually follow the behavior of a physical system at its elemental levels, as “if our faculties and instruments were so sharpened that we could detect and lay hold of each molecule and trace it through all its course.”71 The Teller-Ulam invention invoked a form of Maxwell’s demon to heat a compartment to a temperature hotter than the sun by letting a burst of radiation in, and then, for an equilibrium-defying instant, not letting radiation out. Ulam’s self-reproducing cellular automata—patterns of information persisting across time—evolve by letting order in but not letting order out.

Ulam began imagining how, in a one-dimensional universe, cosmology might evolve. “Has anybody considered the following problem—which appears to me very pretty,” he wrote to von Neumann in February 1949. “Imagine that on the infinite line –∞ to +∞ I have occupied the integer points each with probability say ½ by material point masses—i.e. I have this situation,” and he sketched a random distribution of points on a line. “This is a distribution at time t = 0.”

“Now between these points act 1/d2 forces (like gravitation),” he continued. “What will happen for t > 0? I claim that condensations will form quickly—assume, for simplicity when points touch they stick—with nice Gaussian-like distribution of masses. Then—the next stage—clusters of these condensations will form—somewhat slower but surely (all statements have probability = 1!).” Ulam explained how this simple one-dimensional universe would start to look “somewhat like the real Universe: stars, clusters, galaxies, super-galaxies etc.,” and then considered what might happen in two dimensions, and even three dimensions, by introducing range forces, thermal oscillation, and light. He concluded by suggesting “that ‘entropy’ decreases—an abnormal ‘order’ applies.”

“Only because of our conversation on the bench in Central Park I was able to understand … [that] given is an actually infinite system of points (the actual infinity is worth stressing because nothing will make sense on a finite no matter how large model),” noted Ulam, who then sketched out how he and von Neumann had hypothesized the evolution of Turing-complete (or “universal”) cellular automata within a digital universe of communicating memory cells. The definitions had to be made mathematically precise:

A “universal” automaton is a finite system which given an arbitrary logical proposition in form of (a linear set L) tape attached to it, at say specified points, will produce the true or false answer. (Universal ought to have relative sense: with reference to a class of problems it can decide.) The “arbitrary” means really in a class of propositions like Turing’s—or smaller or bigger.

The Star Maker … could make universes with all kinds of physical and mental attributes. He was limited only by logic. Thus he could ordain the most surprising natural laws, but he could not, for instance, make twice two equal five. —Olaf Stapledon, 1937

Barricelli was an uncompromising nonconformist, questioning accepted dogma not only with regard to Darwinian evolution but on subjects ranging from matter-neutrino transparency to Gödel’s proof.

“The distinction between an evolution experiment performed by numbers in a computer or by nucleotides in a chemical laboratory is a rather subtle one,” he observed.

Information theorists, including Claude Shannon with his 1940 PhD thesis on “An Algebra for Theoretical Genetics” (which was followed by a year at IAS), had already built a framework into which the double helix neatly fit.

“Genes are probably much like viruses and phages, except that all the evidence concerning them is indirect, and that we can neither isolate them nor multiply them at will,” von Neumann had written to Norbert Wiener in November 1946, suggesting that one way to find out how nature makes its copies would simply be to look.

Barricelli played God, on a very small scale. He could dictate the laws of nature, but miracles were out of bounds. The aim, as he explained it in 1953, was “to keep one or more species alive for a large number of generations under conditions producing hereditary changes and evolution in the species. But we must avoid producing such conditions by changing the character of the experiment after the experiment has started.” His guidelines are reminiscent of Leibniz’s belief in a universe optimized to become as interesting as possible under a minimum of constraints.

“Reliable Organizations of Unreliable Elements” (1951).

“The first language and the first technology on Earth was not created by humans,” he wrote in 1986. “It was created by primordial RNA molecules—almost 4 billion years ago. Is there any possibility that an evolution process with the potentiality of leading to comparable results could be started in the memory of a computing machine?”41 Without understanding how life originated to begin with, who could say whether it was possible for it to happen again?

The entire digital universe, from an iPhone to the Internet, can be viewed as an attempt to maintain everything, from the point of view of the order codes, exactly as it was when they first came into existence, in 1951, among the 40 Williams tubes at the end of Olden Lane.

They collectively developed an expanding hierarchy of languages, which then influenced the computational atmosphere as pervasively as the oxygen released by early microbes influenced the subsequent course of life.

They coalesced into operating systems amounting to millions of lines of code—allowing us to more efficiently operate computers while allowing computers to more efficiently operate us. They learned how to divide into packets, traverse the network, correct any errors suffered along the way, and reassemble themselves at the other end.

By representing music, images, voice, knowledge, friendship, status, money, and sex—the things people value most—they secured unlimited resources, forming complex metazoan organisms running on a multitude of individua...

“If humans, instead of transmitting to each other reprints and complicated explanations, developed the habit of transmitting computer programs allowing a computer-directed factory to construct the machine needed for a particular purpose, that would be the closest analogue to the communication methods among cells.”

The barriers between their universe and our universe are breaking down completely as digital computers begin to read and write directly to DNA.

We speak of reading genomes—three million base pairs at a time—but no human mind can absorb these unabridged texts. It is computers that are reading genomes, and beginning to code for proteins by writing executable nucleotide sequences and inserting them into cells. The translation between sequences of nucleotides and sequences of bits is direct, two-way, and conducted in languages that human beings are unable to comprehend.

Wow

When we submit a human or any other animal for that matter to an intelligence test, it would be rather unusual to claim that the subject is unintelligent on the grounds that no intelligence is required to do the job any single neuron or synapse in its brain is doing. We are all agreed upon the fact that no intelligence is required in order to die when an individual is unable to survive or in order not to reproduce when an individual is unfit to reproduce. But to hold this as an argument against the existence of an intelligence behind the achievements in biological evolution may prove to be one of the most spectacular examples of the kind of misunderstandings which may arise before two alien forms of intelligence become aware of one another.

The history of digital computing can be divided into an Old Testament whose prophets, led by Leibniz, supplied the logic, and a New Testament whose prophets, led by von Neumann, built the machines. Alan Turing arrived in between.

“Alan was interested in figures—not with any mathematical association—before he could read,” says his mother, who adds that in 1915, at the age of three, “as one of the wooden sailors in his toy boat had got broken he planted the arms and legs in the garden, confident that they would grow.”

His disarming curiosity lent young Alan “an extraordinary gift for winning the affection of maids and landladies on our various travels,” his mother notes. He was inventive from the start. “For his Christmas present, 1924, we set him up with crucibles, retorts, chemicals, etc., purchased from a French chemist,” she adds. He was nicknamed “the alchemist” in boarding school. “He spends a great deal of time in investigations in advanced mathematics to the neglect of his elementary work,”

Gödel’s incompleteness theorems of 1931 brought Hilbert’s program to a halt. No consistent mathematical system sufficient for dealing with ordinary arithmetic can establish its own consistency, nor can it be complete.

“One of the facets of extreme originality is not to regard as obvious the things that lesser minds call obvious,” says I. J. (Jack)

Originality can be more important than intelligence, and according to Good, Turing constituted proof.

“Henri Poincaré did quite badly at an intelligence test, and Prof also was only about halfway up the undergraduate scale when he took such a test.”

“The way in which he uses concrete objects such as exercise books and printer’s ink to illustrate and control the argument is typical of his insight and originality,” says colleague Robin Gandy. “Let us praise the uncluttered mind.”

Turing introduced two fundamental assumptions: discreteness of time and discreteness of state of mind. To a Turing machine, time exists not as a continuum, but as a sequence of changes of state. Turing assumed a finite number of possible states at any given time.

The Turing machine thus embodies the relationship between a pattern of symbols in space and a sequence of events in time. All traces of intelligence were removed. The machine can do nothing more intelligent at any given moment than make a mark, erase a mark, and move the tape one square to the right or to the left. The tape is not infinite, but if more tape is needed, the supply can be counted on never to run out.

Contrary to Hilbert’s expectations, no mechanical procedure can be counted on to determine the provability of any given mathematical statement in a finite number of steps. This put a halt to the Hilbert program, while Hitler’s purge of German universities put a halt to Göttingen’s position as the mathematical center of the world, leaving a vacuum for Turing’s Cambridge, and von Neumann’s Princeton, to fill.

Engineers avoided Turing’s paper because it appeared entirely theoretical, and theoreticians avoided it because of the references to paper tape and machines.

“When I was a student, even the topologists regarded mathematical logicians as living in outer space,” commented Martin Davis in 1986. “Today, one can walk into a shop and ask for a ‘logic probe.’”17 Turing’s Universal Machine has held up for seventy-six years.

“It is difficult today to realize how bold an innovation it was to introduce talk about paper tapes and patterns punched in them, into discussions of the foundations of mathematics,” Max Newman recalled in 1955.

“Turing’s strong interest in all kinds of practical experiment made him even then interested in the possibility of actually constructing a machine on these lines.”

The title “On Computable Numbers” (rather than “On Computable Functions”) signaled a fundamental shift. Before Turing, things were done to numbers. After Turing, numbers began doing things. By showing that a machine could be encoded as a number, and a number decoded as a machine, “On Computable Numbers” led to numbers (now called “software”) that were “computable” in a way that was entirely new.

Von Neumann “knew Gödel’s work, Post’s work, Church’s work very, very well…. So that’s how he knew that with these tools, and a fast method of doing it, you’ve got the universal tool.”

His PhD thesis, completed in May of 1938 and published as “Systems of Logic Based on Ordinals” in 1939, attempted to transcend Gödelian incompleteness by means of a succession of formal systems, incrementally more complete.

“Gödel shows that every system of logic is in a certain sense incomplete, but at the same time … indicates means whereby from a system L of logic a more complete system L' may be obtained,” Turing explained.

“Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two faculties, which we may call intuition and ingenuity,” Turing explained.

Turing saw the role of ingenuity as “aiding the intuition,” not replacing it.

The relations between patience, ingenuity, and intuition led Turing to begin thinking about cryptography, where a little ingenuity in encoding a message can resist a large amount of ingenuity if the message is intercepted along the way.

Cryptography and cryptanalysis soon became as critical as physics to the course of World War II.

Polish cryptographers had provided a head start by decoding three-rotor Enigma messages before the outbreak of the war. Three young Polish mathematicians (Henryk Zygalski, Jerzy Rózycki, and Marian Rejewski), assisted by French intelligence and with an interest in the German Enigma dating back to an interception by Polish customs officers in 1928, narrowed the search for rotor configurations so that electromechanical devices (called “bombas” by the Poles and “bombes” by the British) could apply trial and error to certain subsets that remained.