A.K. Dewdney, Scientific American 252 (May 1985) 18.Building computers in one dimension sheds light on irreducibly complicated phenomena

Immersed as we now are in a world of artificial computers it is interesting to consider the possibility that we are also surrounded by natural ones. Computers made of water, wind and wood (to mention just a few possibilities) may be bubbling, sighing or quietly growing without our suspecting that such activities are tantamount to a turmoil of computation whose best description is itself. This is not to say that such natural systems compute conventionally, only that their structure makes computation a possibility that is latent.

An eloquent exponent of this insight is Stephen Wolfram, a theoretical physicist at the Institute for Advanced Study in Princeton. Wolfram notes that a turbulent flow of fluid or the growth of a plant consists of rather simple components whose combined behavior is so complex that it may not be reducible to a mathematical statement—its best description is itself. The irreducibility of a natural system would follow from a demonstration of its ability to store, transmit and manipulate information, that is, to its ability to compute. In the September 1984 Scientific American Wolfram describes the use of cellular automata to explore this possibility. He proposes to find a cellular automation that both computes and mimics a natural system. Wolfram’s search focuses on the simplest of all possible cellular automata, those that have only a single dimension.

Such automata consist of simple elements that combine to generate complexity. Wolfram suggests that lurking among them are true computers, vast linear arrays of cells blinking from state to state and churning out any calculation a three-dimensional computer is capable of. Wolfram, currently searching through the myriad of one-dimensional cellular automata, is not above enlisting the help of amateurs in this daring and sophisticated enterprise. I shall describe the search and its consequences for natural computers in more detail below.

Before embarking on that adventure readers are invited on a short journey (computationally speaking) from the land of three dimensions down to the unbelievably narrow confines of one dimension. A good jumping-off place is three-dimensional computers, the ones currently inhabiting offices, factories and homes. They consist of fairly simple elements linked in a complex way. I speak here not of input or output devices but of the heart of the machine, a tiny silicon chip housing thousands of logic gates, memory elements, registers and other components. All of these are connected by an elegant pattern of tiny wires. The fact that the circuitry clings to a silicon surface does not mean it is two-dimensional. For one thing, when two connections cross, one must pass under the other. In addition, the silicon substrate of the circuitry mediates the function of every logic component.

Two-dimensional computers are to be found only in spaces with two dimensions, such as the Planiverse [see “Bibliography,” page 144]. This realm is inhabited by a race of beings called Ardeans. The Ardeans have apparently succeeded in constructing a two-dimensional computer using just one type of logic element. We call it a NAND gate. Its output is a 1 if at least one of its inputs is a 0. Not only can a computer be constructed entirely from such gates but also the thorny problem of crossed connectors can be solved. The Ardeans create a special plane circuit from 12 NAND gates so that two signals entering the circuit from the left in order ab leave on the right in order ba. Hence two signals may be crossed even if connections cannot. At the same time, the number 12 seems a bit excessive and the Ardeans would be grateful to any readers who can find a simpler NAND circuit that still enables signals to cross.

There is also a discrete two-dimensional space called Life, a game invented by John Horton Conway, the well-known University of Cambridge mathematician. Readers will remember this engaging exercise from “Mathematical Games” columns by Martin Gardner. As recently as October, 1983, Brian Hayes described in this department how the game could be realized in a spreadsheet program. Life is an infinite two-dimensional lattice of square cells whose states are influenced by the states of neighboring cells. Time is also discrete and from one tick of a cosmic clock to the next each cell is either alive or dead depending on a set of very simple rules:

If a cell is dead at time t, it comes alive at time t + 1 if, and only if, exactly three of its eight neighbors are alive at time t.
If a cell is alive at time t, it dies at time t + 1 if, and only if, fewer than two or more than three neighbors are alive at time t.

With this set of rules everywhere in effect on Life’s lattice, an initial configuration of live cells may grow interminably, fall into a cyclic pattern or eventually die off. Through more than a decade of experimentation by Life enthusiasts it has become clear that Life is far more complicated than anyone had thought.

For one thing, it has turned out that computers can be constructed within Life’s cellular space. The discovery came incrementally over a period of a few years. In 1969, shortly after he designed the game, Conway discovered a curious little pattern now called a glider. It blinked through four generations only to recover its original form at a location displaced diagonally by the space of one cell. On a monitor displaying the output of a particularly fast Life program a glider resembles a small creature from an exobiologic fantasy, wiggling its tail as it crawls across the screen. It travels at one-fourth the speed of light (in a cellular sense).

Although no one recognized it at the time, here was a medium of communication for use in a two-dimensional Life computer: instead of electronic pulses, use gliders!

The next step in the construction came in 1970 with the discovery by R. William Gosper, Jr., and several colleagues of a glider gun. Gosper, then a student at the Massachusetts Institute of Technology, was keen on collecting the $50 prize that Conway had offered in Gardner’s column. The prize would go to the first person who demonstrated conclusively that an initial configuration could grow without limit. Gosper’s glider gun spewed out a new glider every 30 moves. The gun and the gliders constituted an ever growing population of live cells.

Besides Gosper there were other students at M.I.T. pursuing Life in their spare time. One of these was Michael D. Beeler, who particularly enjoyed the analogy between Life and particle physics. Beeler trained a beam of one or more gliders on various targets, carefully noting the sometimes boring and sometimes spectacular results of the collisions. He even sent two beams of gliders into each other in various ways. His persistence was rewarded by some useful observations.

One such observation was that two gliders could collide and annihilate each other. This made possible the construction of the next component of a computer, logic gates. The simplest of these was a NOT gate. It changes one logic signal into together; 0 input becomes 1 output and vice versa. Life’s NOT gate is constructed as follows. Set up a glider gun to send gliders in a specified direction. Binary numbers to be input to the NOT gate are encoded in a second stream of gliders aimed at right angles to the first one. In the input stream a glider may be present (a 1) or absent (a 0). This stream intersects the stream from the glider gun in such a way that when two gliders collide, they annihilate each other. This means that a glider in the input stream punches a hole in the glider-gun stream, converting a glider (1) into a nonglider (0) in the process. The absence of a glider in the input stream allows a glider from the gun to pass through unmolested. In this way a 0 is converted into a 1. Interestingly, the NOT gate has no structure to speak of: apart from its resident glider gun, it is merely a place where gliders meet. The construction of other gate types such as an AND gate and an OR gate also involves interacting streams of gliders, but it is too complicated to present here.

Memory and other registers are constructed through the interaction of gliders with four-cell configurations called blocks. A single bit of memory is encoded by the position of a block. The block is moved backward or forward by teams of gliders. Two gliders on appropriately chosen courses suffice to move the block three spaces in one direction after crashing into it. Ten gliders directed with equal care will return it to its original place.

There is much ingenuity and interest in the rest of the construction. It is all available in the delightful book Winning Ways for Your Mathematical Plays, by Elwyn R. Berlekamp, John H. Conway and Richard K. Guy. The book is divided into three sections: two-person games, one-person games and no-person games. Life is described in the last section.

In descending the final step down to one dimension there are only cellular spaces to consider; it is hard to imagine how the Ardeans could reduce their computer to a single continuous line. At first glance cellular space seems nearly as restrictive as that line. We are compensated for decreased dimensionality, however, in not being limited to a single set of rules. Instead we are given the opportunity to make our own rules. Additional compensations arise from the very simplicity of such linear spaces and from the fact that hundreds of generations can be viewed at a glance: place an initial pattern on a line and compute successive generations on successive lines down the page or display screen. A space-time diagram will develop.

A one-dimensional cellular automaton (hereafter called a line automaton) consists of an infinite strip of cells changing states according to a given set of rules. As in the game of Life a cosmic clock ticks away and at each tick every cell enters a state determined by its previous state and the previous states of cells in its neighborhood. A line automaton is specified by giving two numbers called k and r as well as a set of rules for deriving the next state of a cell. The first number, k, determines how many states are allowed for each cell. In Life there are just two states and so k is equal to 2; among the line automata to be considered, higher values of k are common. The second number, r, refers to the radius of neighborhoods used to compute the next state of a cell. The present state of a cell and the states of its r neighbors on both sides determine the next state of the cell. For example, if r is equal to 2 and k is equal to 3, a certain rule might specify that when a cell’s neighborhood looks like

| 0 | 2 | 1 | 1 | 0 |

the next state occupied by the central cell would be

| 2 |

The set of rules that defines a given line automaton must decide the fate of a cell for every possible configuration of states inhabiting its neighborhood. Depending on the size of k and r the number of possible rule sets to consider can be enormous. For example, given the modest values of k and r described above, there are more line automata than there are atoms in the known universe.

Clearly each person on this planet can pick and choose his or her own personal line automaton. Indeed, I have already selected one for myself. For reasons that will soon be clear it is called Ripple. Ripple allows three states for each cell; each neighborhood consists of three cells, a central cell and two cells flanking it. The rules of Ripples are reasonably straightforward and easily programmed:

1. If a cell is in state 0, its next state will be 2 if its flanking states add up to 2 or more. Otherwise its next state will be 0.

2. If a cell is in state 1, its next state will be 0.

3. If a cell is in state 2, its next state will be 1 if either of the flanking cells is in state 0. Otherwise its next state will be 2.

I am sure that Ripple is not about to replace Life; Ripple was designed to illustrate some of the more interesting possibilitites line automata offer. For example, Ripple has simple gliders and an even simpler glider gun.

Assume that Ripple’s cellular space is entirely in state 0 except for two adjacent cells. The cell on the left is in state 2 and the other is in state 1. At the next generation this pattern will have shifted by one cell to the left. Undisturbed, the two-cell glider will ripple silently to the left forever. Interchange the states of the two cells and a right-moving glider is created. The glider gun consists of a single cell in state 2. That cell cycles through states 1, 0 and then back to 2, issuing a pair of gliders on each cycle. I wonder if anyone can find a gun in Ripple that emits gliders in a single direction only.

Simultaneous activation of a pair of such glider guns produces strange effects. In the process of mutual annihilation the resulting explosions send gliders off in both directions. If the guns are an even number of cells apart, this number of gliders go off in both directions. Otherwise a single gun remains in the middle and shoots out gliders in an interminable stream.

Ripple is just one line automaton. What of the others? The number of possible rule sets to consider is greatly reduced by adopting the ones Wolfram calls totalistic. Here the next state of a given cell is determined only by the sum of the states in the cell’s neighborhood. The sum includes the state of the given cell. The number of possible sums varies from 0 to m, where m is the largest value of state multiplied by the size of the neighborhood. If one specifies how these sums become the central cell’s next state, one has specified the line automaton completely.

For example, there is a very interesting line automaton governed by totalistic rules given in this table:

sum	| 5 | 4 | 3 | 2 | 1 | 0 |
next state	| 0 | 1 | 0 | 1 | 0 | 0 |

Here k and r are both equal to 2; the possible values of the sum of states in a five-cell neighborhood vary from 0 to 5. Wolfram calls this set of rules number 20 because the six next-state values in the table represent the number 20 written in binary notation.

There are 64 ways in all that the second row of the table can be filled in. Each one results in a line automaton and Wolfram has examined all 64 of them. Needless to say, a computer is essential in such an investigation. To determine the behavior of a given line automaton, Wolfram forms an initial pattern of some 100 cells in random states and then turns the automaton loose on the pattern. To nullify the effects of the vast arrays of zeros on each side of the pattern, Wolfram makes the left end of the initial pattern contiguous with the right end. This turns the pattern into a circle and its history becomes a cylinder, yet the result is the same as if the initial random pattern were repeated indefinitely in both directions of the original cellular space. In any event the effect of line automata on such random input patterns is surprisingly uniform. Each automaton will fall into one of four broad classes constructed by Wolfram:

Class 1. After a finite number of generations the pattern deteriorates into a single homogeneous state endlessly repeated.
Class 2. The pattern evolves into a number of unvarying or periodic subpatterns.
Class 3. The pattern never develops any structure. Space-time diagrams look chaotic.
Class 4. The pattern develops complex localized subpatterns, some of them long-lasting.

Of the 64 automata in which k and r are both equal to 2, 25 percent are in class 1, 16 percent are in class 2, 53 percent are in class 3 and only 6 percent are in class 4. Wolfram suspects that computers might be found in the fourth class. For example, the line automaton with code number 20 is in class 4.

As though encouraging Wolfram in the search, the code-20 automaton has cheerfully disclosed some gliders. They are 10111011 and 1001111011. Both gliders move to the right. Totalistic rules are always symmetrical; to obtain left-moving gliders merely reverse these patterns. Is there a gun for such gliders in the code-20 space? Wolfram thinks there is. But there is another space where he has yet to find even a glider! It is the code-792 space. When we write this number in ternary notation, we obtain a set of rules for a 3-state line automaton:

sum	| 6 | 5 | 4 | 3 | 2 | 1 | 0 |
next state	| 1 | 0 | 0 | 2 | 1 | 0 | 0 |

The search for gliders and glider guns calls for the advice of a separate document, which I have persuaded Wolfram to write. It describes an algorithm that hunts for what Wolfram calls persistent structures. Adventurous readers may write to “Glider Gun Guidelines,” Scientific American, 415 Madison Avenue, New York, N.Y. 10017. Please send $3 to cover the cost of mailing.

The search for gliders and glider guns focuses on a number of line automata thought to be computation universal. In other words, these are line automata capable of acting like a computer. Besides the code-20 and code-792 automata already discussed, there is the two-state line automaton (r = 3, code number 88) in which a glider gun has already been found.

James K. Park, a student at Princeton University, found the gun in that automaton. Readers who would like to witness Park’s glider gun in operation must write a simple program for displaying the generations of a line automaton and for deriving one generation from the next. It is an easy matter to implement line automaton 88 with such a program: when you are ready, input the initial pattern 1111111111011 and watch it expand and contract. The gun spews out a glider in each direction once every 238 generations.

Rather than implement a specific automaton, readers are advised to write a program that takes arbitrary totalistic rules as input. This is easy to do for fixed values of k and r and almost as easy if these parameters are allowed to vary. Use a special array called table for the rules and two linear arrays called newcells and oldcells to hold the new and the old patterns currently being processed. Make the two arrays as wide as you like but bear in mind that a display screen (depending on the type of display) may show only a limited part of these arrays. Display the largest middle part of newcells that fits and cycle through the following steps: Transfer the contents of newcells into oldcells. Scan oldcells; for its ith member add up the value of oldcells from i – r to i + r. Look up the resulting sum in table and transfer the state value so found to the ith member of newcells. Next reenter the computational cycle in the display phase and repeat it. Displays can be successive or stationary. In the former case a space-time diagram results; in the latter case one watches a kind of one-dimensional motion picture.

As noted above, a line automaton is called computation-universal if as generation succeeds generation there is an initial pattern capable of acting like a computer. Part of the initial pattern is the input and part of some later pattern is the output. Is it really possible to build such a computer out of glider guns and various other pieces of cellular hardware? Wolfram thinks it is. In one of the line automata currently under investigation gliders have been found that pass through certain stable subpatterns. This gives hope that the transmission of information within a linear computer need not be blocked by components unconcerned with that information. In addition to Wolfram there are other workers currently experimenting with line automata. Kenneth Steiglitz of Princeton is one of them. He has found gliders that have properties like those of solitons. Such gliders can even pass each other!

Will we eventually find persistent structures capable of moving, storing and manipulating information in a one-dimensional cellular realm? Perhaps not. It may be that there is something inherently quite different about cellular computation in one dimension, something that requires us to look at computing in an entirely new way.

Wolfram has fantasized freely about how line automata illuminate the behavior of automata in general, and how they in turn provide insight into natural processes. Suppose one were to find a line automaton that closely mimics some natural process, for example a turbulent flow of liquid or gas, the motion of particles under the influence of forces, or even a biological process such as growth. Suppose further the automaton turned out to be computation-universal. In other words, not only can its space contain an explicit structure that computes but also the same space contains the computer implicitly: any attempt to predict the behavior of the automaton would by definition be attempting to predict the actions of a general-purpose computer. This in general cannot be done except by the same kind of device, another general-purpose computer. It follows that no short cut would be available for predicting the behavior of the corresponding natural system. Its processes would be computationally irreducible in the sense that the predicting mechanism (whether formula or computer) must simulate the system in question more or less directly.

This conclusion brings us back to Ripple. An initial population of gliders going in random directions bounce off one another. Sometimes their collisions result in a glider gun, which produces more gliders, and sometimes their collisions produce nothing. It reminds me of a miniature one-dimensional universe filled with elementary particles rippling back and forth. Thus I have reversed the order of Wolfram’s search. Starting with a strip automaton that behaves vaguely like a system of particles (odd ones at that), I have a dream that Ripple is computation-universal. Since it is my own personal automaton, I may be dreaming alone.

Last June’s column on analog gadgets is producing such a deluge of material from different parts of the world that the subject seems worth revisiting, even though the September 1984 column also carried a reprise.

It is interesting to note that some gadgets of truly practical value have emerged. By a practical analog gadget I mean something like the atmospheric control system described by Homer B. Clay, a consulting engineer in Phoenix, Ariz. Clay was called in to help a printer control temperature and humidity in his plant. Temperature and humidity are critical because they affect the state of the carbon black that coats large copper rollers used in some printing processes. An experienced printer can hold a sheet of carbon black and tell by the amount of droop whether it is in a suitable state. When it is not suitable (because of incorrect moisture content or temperature), the carbon black wrinkles or cracks. Clay devised a more or less standard circuit to sense the temperature and humidity conditions and turn a spray system on or off to control them. The system apparently worked for a short time, until unseen variables threw it out of kilter.

Returning to the printing plant one day to evaluate his control system, Clay was led back to the printing area by a grinning plant engineer. Clay had some trouble believing what he saw: “Our little system was disconnected and in its place was a small strip of carbon black, one end fixed to the shelf, the other end free to move. When the droop was ‘just right,’ the free end closed a pair of contacts, turning on the sprays.” The plant engineer rubbed it in by commenting, “Works like a charm.”

Back in 1948 Robert Heppe of Fairfax, Va., was a freshman electrical engineer at the Queens, N.Y., plant of the Sylvania Electric Products Company. Heppe, assigned to assist in the design of vacuum tubes, found the process onerous. The problem was that one had to specify the size, shape and placement of the grids and beam-forming plates on paper. The design was then manufactured in the form of a single tube and tested. This could take several days. His supervisor, Gerald Rich, improved efficiency by suggesting a certain analog gadget.

The gadget consisted of a rubber sheet, a dowel, some plywood and several boxes of toothpicks. The rubber sheet clamped into a large ring represented the tube cross section magnified many times. The cathode was a wood dowel poking up in the center of the sheet. Arrays of toothpicks represented various grid designs. Negative grids tented the sheet up from below; positive grids depressed the sheet from above. Other aspects of tube geometry were captured by plywood shapes also imposed from below or above. Electrons pouring from the cathode were simulated by slowly emptying a can of BB’s over the dowel. “It can be shown,” writes Heppe, “that the slope of the rubber in such a gadget represents the electric field, and the height represents the voltage in the space between the electrodes…. The BB’s rolled down the sheet [as in] a pin-ball game, some collecting at the plate, some at the positive grids. If we didn’t like how many arrived at the various electrodes, or which way they went, we could move things around, change sizes, etc., and try it again.” Promising configurations were embodied and tested in real tubes.

Many other readers offered examples. There was a hemocrit to measure solid fractions in human blood, invented by Dr. Alan Kwasman of Loma Linda, Calif. Mathias Soop of the European Space Agency in Darmstadt, West Germany, presented a string, nail and paper-clip gadget. The device illustrates an analog solution to the problem of minimizing thruster fuel consumption while controlling satellite attitude.

Readers also recalled analog gadgets of wider utility: the three-arm protractor used in coastal navigation, the range finder employed by U.S. naval forces in World War II and the planimeter, a marvelously simple instrument that serves to measure the area of a plane surface.

The best and biggest of analog gadgets are analog computers. These are alive and well at Electronic Associates, Inc., a manufacturer of analog equipment in West Long Branch, N.J. I was even invited to the plant to witness the superiority of these machines over the humble devices presented last June.