In [Feynman82], Richard Feynman seems to say that CAs cannot be a perfect model for the world because nature does in fact have action at a distance in the form of the kind of quantum mechanical synchronicities discussed by the Einstein-Podolsky-Rosen paradox. But it is possible to write programs similar to CAs in which the cells do occasionally look at distant neighbors.
U.S. Patent Number 4,691,291, “Random Sequence Generators”, granted September 1, 1987. Wolfram has also patented a hexagonal-cell cellular automaton for simulating systems described by partial differential equations; see U.S. Patent Number 4,809,202, granted February 28, 1989.
The interdisciplinary conference CA 84 held at MIT in early summer of 1984, attracted some 150 participants.
The real reason is that if EveryCell could see eight bits of each neighbor, then a “situation” would consist of 8×9 = 72 bits, and our exhaustive lookup table would have a crippling 272 entries. 272 ≈ 270 = 210 7 = 1 K7 ≈ (One Thousand)7 = 1,000,000,000,000,000,000,000 = One Sextillion. No way. Seeing two bits of each neighbor is almost feasible; you'd need a 224 entry table, and 224 = (24) × (220), or 16 Meg lookup table. Meg is K's big sister and means about a million. Actually a lot of our rules (like Ranch) do look at two bits of each neighbor; we do it by running a rule that has two alternating cycles, looking at bit #0 in cycle 0 and at bit #1 in cycle 1. Sometimes people say that no programs need all the new RAM and processor speed being developed. That's not true. Cellular automata freaks can eternally sop up whatever the chipsters have ready.
See [Dewdney88], pp. 135-148 for a good introductory discussion of one-dimensional CAs. Among other treasures, [Wolfram86] has several very comprehensive discussions of 1D CAs.
In some programming languages, (A − B) MOD 2 can return the negative value −1, which will upset the rule maker, causing it to emit error messages. An easy way to avoid this is to write (2 + A − B) MOD 2 to ensure a positive value. An alternative method, if you know that A and B are both zero or one, is to write A XOR B.
The Sierpiński gasket is a shape you get by repeatedly dividing a triangle into four subtriangles by connecting the triangle's median points, then removing the middle triangle, and applying the same process to the three remaining triangles. The name was coined by Benoit Mandelbrot [Mandelbrot82], in homage to the set-theorist Wacław Sierpiński, but the pattern can also be found in Pascal's triangle, as the result of a chaotic iteration [Peitgen&Saupe88], p. 224, and as the output of the 1-D version of Fredkin's parity rule.
If we keep B down to 1, then EveryCell has 9 bits of situation: one bit of self and eight bits of neighbor. So the lookup table has 29 or 512 lines. If each NewState is again a single bit, this makes for 2512 ways to fill in the table. 2512 is a good deal larger than googol, or 10100. If B is 4, then EveryCell has 12 bits of situation: four bits of self and eight bits of neighbor. If the new state is to be another four bit state, we have 24 choices for each line of a 212 line lookup table, which makes for (24)2 12 = 24 × (2 12) = 2((2 2) × (2 12)) = 22 14 = 216 K = 24 × (4 K) > 104 K > the decimal number written as a one with four thousand zeroes after it.
[Margolus&Toffoli87], pp. 41–42 and pp. 70–71.
[Margolus&Toffoli87], pp. 72–75. WebCA uses a pseudorandom number generator.
Stephen Wolfram refers to such rules as “legal” rules, see [Wolfram86], p. 9.
[Poundstone85], pp. 33–37. John Horton Conway, the inventor of Life, discovered the glider while watching the evolution of the R pentomino. The R pentomino was first tracked all the way to its final state in 1970.
[Silverman87], p. 51–54. See also [Margolus&Toffoli87], pp. 47–49.
The way I got this estimate was by following these steps:
You can also use the population census to make such estimates.
If n=0, then the rule has no refractory states, meaning that state 1 goes directly back to state 0. This means, in turn, that conditions (ii) and (iv) can be omitted and that condition (ii) would read “A cell in state 1 goes to state 0.” The Brain 0LU rules are ugly, with a nasty flicker.
[Rucker82], pp. 38–39. Software has three main characters: young Sta-Hi, old Cobb Anderson, and Ralph Numbers, the first truly living robot. In the scene where Rainbow appears, Sta-Hi has fallen into the hands of a demented redneck cyberpunk gang called the Little Kidders. The little Kidders are Kristleen, Filthy Phil, Haf'n'Haf, Rainbow, and her boyfriend Berdoo. They have Sta-Hi tightly bound, with his head sticking up through a hole in the middle of a table.
“It's a stuzzy high, Rainbow,” Phil told her. With the fat and the short hair he looked stupid, but his way of speaking was precise and confident. He seemed to be the leader. “This should be a good brain, too. Full of chemicals, I imagine.”
Haf'N'Haf seemed to be having some trouble starting the little cutting machine up. It was a variable heat-blade. They were going to cut off the top of Sta-Hi's skull and eat his brain with those cheap steel spoons. He would be able to watch them…at first.
Someone started screaming. Someone tried to stand up, but he was tied too tightly. The variable blade was on now, set at one centimeter. The thickness of the skull.
Sta-Hi threw his head back and forth wildly as Haf'N'Haf leaned towards him. There was no way to read the ruined face's expression.
“Hold still, damn you!” Kristleen shouted. “It's no good if we have to knock you out!”
Sta-Hi didn't really hear her. His mind had temporarily snapped. He just kept screaming and thrashing his head around. The sound of his shrill voice was like a lattice around him. He tried to weave the lattice thicker.
Berdoo went and got a towel from the bathroom. He wedged it around Sta-Hi's neck and under his chin to keep the head steady. Sta-Hi screamed louder, higher.
“Stuff his mayouth,” the green-haired girl cried. “He's yellin and all.”
“No,” Phil said. “The noise is like…part of the trip. Wave with it, baby. The Chinese used to do this to monkeys. It's so wiggly when you spoon out the speech-centers and the guy's tongue stops moving. Just all at—” He stopped and the flesh of his face moved in a smile.
Sta-Hi's given name is Stanley Hilary Mooney, Jr. Hearing of Sta-Hi's narrow escape (he does escape), Stan Sr.'s reaction is this:
Mooney felt trembly all over. He could only see the horrible image of his son's dying eyes watching the Little Kidders chew up his last thoughts. Mooney's tongue twitched, trying to flick away the imagined taste of the brain tissue, tingly with firing neurons, tart with transmitter chemicals.
The full name is the Belousov-Zhabotinsky reaction. If you put certain chemicals in a petri dish with a sprinkling of a catalytic powder you actually see the Zhabotinsky reaction taking place. The reaction was first reported in the 1960s. A discussion of it can be found in [Winfree74]. [DewdneyColumn88a] discusses a Zhabotinsky style CA called the HodgePodge machine—the Hodge program is based on this column. See my discussions of Hodge, Rainzha, and Zhabo in the Rules chapter.
169×16 is about 2×10176, or more accurately: 247, 330, 401, 473, 104, 534, 060, 502, 521, 019, 648, 190, 035, 131, 349, 101, 212, 939, 914, 063, 056, 092, 897, 225, 106, 531, 867, 170, 316, 401, 061, 243, 044, 989, 597, 671, 426, 016, 139, 339, 351, 365, 034, 306, 741, 209, 967, 546, 155, 101, 893, 167, 916, 606, 772, 148, 699, 136.
See [Wolfram86], p. 95 and [Langton86], p. 129.
This is taken directly from [Margolus&Toffoli87], p. 123. Margolus developed this technique as a simplification of the so-called HPP lattice gas which was introduced in, J. Hardy, O. de Pazzis, & Y. Pomeau, “Molecular Dynamics of a Classical Lattice Gas,” Phys. Rev. A 13, 1976, pp. 1949–1960.
This quote is from the December, 1949, Illinois lectures, reprinted in [VonNeumann66], p. 77.
This is from the September, 1948, lecture [VonNeumann51], p. 315. This weird scenario is reminiscent of a big scene in Kurt Vonnegut, Jr.'s Sirens of Titan, where an unhappy robot tears himself apart and floats the pieces in a lake.
[Ulam50], p. 336
See the three essays coauthored by Ulam in the collection [Burks70].
See [Gardner71]. See also [Levy84] for a good section about Gosper and the early excitement over Life among the users of the PDP-6 computer at the MIT Artificial Intelligence Project. On p. 147, Levy has a nice quote from Gosper, telling how he saw Life as a way to
… basically do new science in a universe where all the smart guys haven't already nixed you out two or three hundred years ago. It's your life story if you're a mathematician: every time you discover something neat, you discover that Gauss or Newton knew it in his crib. With LIFE you're the first guy there, and there's always fun stuff going on. You can do everything from recursive function theory to animal husbandry. There's a community of people who are sharing their experiences with you. And there's the sense of connection between you and the environment. The idea of where's the boundary of a computer. Where does the computer leave off and the environment begin?
See [BerlenkampConway&Guy82], Vol. 2, or [Poundstone85]. The significance of Conway's proof is not that he shows that some cellular automaton can act as a universal computer, for von Neumann already proved this in [VonNeumann66]; and for that matter Alvy Ray Smith's Stanford dissertation of 1970 describes a universal one-dimensional CA computer. The significance of Conway's proof is that he shows that the specific rule of the Game of Life can itself act as a universal computer.
The WebCA rule FredMem is the Parity rule with seven bits of memory. If you use the color palette Mask1 with FredMem you will see the Parity rule.
See Robert Wright's article about Fredkin in The Atlantic, April, 1988. This article reappears as a chapter in Wright's 1988 book, Three Scientists and Their Gods.
This was Stephen Levy, author of Hackers. Levy's editor at Rolling Stone also found cellular automata too esoteric, so it appeared as [Levy85] in the Whole Earth Review.
The rule they showed me was Critters, [Margolus&Toffoli87], pp. 132–134.
On this same trip I went to see the MPP at Goddard; they'd invited me there to give a talk on my book The Fourth Dimension [Rucker84]. The MPP was a roomful of equipment behind a thick glass window. When I asked its keeper if he'd ever run the Game of Life on it, he looked at me like I was out of my mind. As far as I could make out, NASA uses the MPP to enhance satellite photos. The Connection Machine® from Thinking Machines, Inc., of Cambridge, Mass., is a much sexier parallel processing machine. The Connection Machine has 64,000 processing chips (see [Hillis88]). Visitors to the cellular automaton conference CA86 at MIT were invited over to the Thinking Machines offices to see the Connection Machine running cellular automata and simulating a wind-tunnel. Stephen Wolfram consulted with Thinking Machines for a short while before setting off on his own to build and distribute the mathematics program Mathematica.
Wolfram's papers are collected, along with numerous papers by other authors, in the excellent volume, [Wolfram86].
The first few paragraphs of this section are taken from [Rucker88a].
I called the disk Freestyle CA, and sold about a hundred of them for $10 each via announcements in the magazine Science Fiction Eye, the newsletter Amygdala, and the Whole Earth book Signal. Since all the Freestyle CA programs have evolved into radically improved forms in CelLab, the Freestyle CA disk is now obsolete and unavailable.