WIlliam Poundstone - The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge

The Recursive Universe

Cosmic Complexity and the Limits of Scientific Knowledge

William Poundstone

Dover Publications, Inc., Mineola, New York

Copyright
Copyright 1985, 2013 by William Poundstone
All rights reserved.

Bibliographical Note

This Dover edition, first published in 2013, is a republication of the work originally published in 1985 by William Morrow and Company, Inc., New York. For this edition the author has proided a new Afterword and the section Life for Home Computers has been omitted.

International Standard Book Number

eISBN-13: 978-0-486-31579-9

Manufactured in the United States by Courier Corporation
49098X01
www.doverpublications.com

To my parents

ACKNOWLEDGMENTS

The game of Life was invented by John Horton Conway of the University of Cambridge. Martin Gardner introduced Life through his October 1970 Scientific American column. Interest in the game soon spawned a newsletter, Lifeline, published by Robert T. Wainwright from 1971 to 1973. Much of what is known of the Life universe is the work of Lifelines many correspondents. Among those who have contributed to this book through their discoveries and insights are Simon Norton, Gary Filipski, Brad Morgan, Ranan B. Banerji, D. M. Saul, Robert April, Michael Beeler, R. William Gosper, Jr., Richard Howell, Rich Schroeppel, Michael Speciner, Keith McClelland, Thomas Holmes, Michael Sporer, Philip Stanley, Donald Woods, William Woods, Roger Banks, Sol Goodman, Arthur C. Taber, Robert Bison, David W. Bray, Charles L. Corderman, Gary Goodman, Stephen B. Gray, Maxwell E. Manowski, Clement A. Lessner III, William P. Webb, Hugh Thompson, Robert Kraus, Rici Liknaitsky, Bill Mann, Steve Ward, James F. Harford, Curt Gibson, Jan Kok, Douglas G. Petrie, Philip Cohen, Paul Wilson, V. Everett Boyer, Dave Buckingham, Mark Niemiec, Peter Raynham, Dean Hickerson, Paul Schick, and George D. Collins, Jr. The information on relative frequencies of Life objects is largely the work of Hugh Thompson. The photograph of the breeder is from Gospers group at MIT. The dedicated Life computer used for this books research was constructed by George Wells.

CONTENTS

The Recursive Universe

COMPLEXITY AND SIMPLICITY

In the early 1950s, the Hungarian-American mathematician John Von Neumann was toying with the idea of machines that make machines. The manufacture of cars and electrical appliances was becoming increasingly automated. It wasnt hard to foresee a day when these products would roll off assembly lines with no human intervention whatsoever. What interested Von Neumann particularly was the notion of a machine that could manufacture itself. It would be a robot, actually. It might wander around a warehouse, collecting all the components needed to make a copy of itself. When it had everything, it would assemble the parts into a new machine. Then both machines would duplicate and there would be four... and then eight... and then sixteen...

Von Neumann wasnt interested in making a race of monster machines; he just wondered if such a thing was possible. Or does the idea of a machine that manufactures itself involve some logical contradiction?

Von Neumann further wondered if a machine could make a machine more complex than itself. Then the machines descendants would grow ever more elaborate, with no limit to their complexity.

These issues fascinated Von Neumann because they were so fundamental. They were the sorts of questions that any bright child might ask, and yet no mathematician, philosopher, scientist, or engineer of the time could answer them. About all that anyone could say was that all existing machines manufactured machines much simpler than themselves. A labyrinthine factory might make a can opener.

Many of Von Neumanns contemporaries were interested in automatons as well. Several postwar college campuses boasted a professor who had built a wry sort of robot pet in a vacant lab or garage. There was Claude Shannons Theseus, a maze-solving electric rodent; Ross Ashbys machina spora, an automated fireside cat or dog which only stirs when disturbed, by one account; and W. Grey Walters restless tortoise. The tortoise scooted about on motorized wheels, reacting to obstacles in its path but tending to become fouled in carpet shag. When its power ran low, the tortoise refueled from special outlets.

Von Neumanns hunch was that self-reproducing machines are possible. But he suspected that it would be impractical to build one with 1950s technology. He felt that self-reproducing machines must meet or exceed a certain minimum level of complexity. This level of complexity would be difficult to implement with vacuum tubes, relays, and like components. Further, a self-reproducing automaton would have to be a full-fledged robot. It would have to see well enough to recognize needed components. It would require a mechanical arm supple enough to grip vacuum tubes without crushing or dropping them, agile enough to work a screwdriver or soldering iron. As much as Von Neumann felt a machine could handle these tasks in principle, it was clear that he would never live to see it.

Inspiration came from an unlikely source. Von Neumann had supervised the design of the computers used for the Manhattan Project. For the Los Alamos scientists, the computers were a novelty. Many played with the computers after hours.

Mathematician Stanislaw M. Ulam liked to invent pattern games for the computers. Given certain fixed rules, the computer would print out ever-changing patterns. Many patterns grew almost as if they were alive. A simple square would evolve into a delicate, corallike growth. Two patterns would fight over territory, sometimes leading to mutual annihilation. Ulam developed three-dimensional games too, constructing thickets of colored cubes as prescribed by computer.

Ulam called the patterns recursively defined geometric objects. Recursive is a mathematical term for a repeated procedure, in this case, the repeated rules by which the computers generated the patterns. Ulam found the growth of patterns to defy analysis. The patterns seem to exist in an abstract world with its own physical laws.

Ulam suggested that Von Neumann construct an abstract universe for his analysis of machine reproduction. It would be an imaginary world with self-consistent rules, as in Ulams computer games. It would be a world complex enough to embrace all the essentials of machine operation but otherwise as simple as possible. The rules governing the world would be a simplified physics. A proof of machine reproduction ought to be easier to devise in such an imaginary world, as all the nonessential points of engineering would be stripped away.

The idea appealed to Von Neumann. He was used to thinking of computers and other machines in terms of circuit or logic diagrams. A circuit diagram is a two-dimensional drawing, yet it can represent any conceivable three-dimensional electronic device. Von Neumann therefore made his imaginary world two-dimensional.

Ulams games were cellular games. Each pattern was composed of square (or sometimes triangular or hexagonal) cells. In effect, the games were played on limitless checkerboards. All growth and change of patterns took place in discrete jumps. From moment to moment, the fate of a given cell depended only on the states of its neighboring cells.

The advantage to the cellular structure is that it allows a much simpler physics. Basically, Von Neumann wanted to create a world of animated logic diagrams. Without the cellular structure, there would be infinitely many possible connections between components. The rules needed to govern the abstract world would probably be complicated.

So Von Neumann adopted an infinite checkerboard as his universe. Each square cell could be in any of a number of states corresponding roughly to machine components. A machine was a pattern of such cells.