In [Feynman 84], 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.
See [Dewdney88], pp. 149-159. In the terminology of our Chapter 4, 2D Life is NLUKY 03323 and the Bays rule we call Life3D is NLUKY 05545. The names "Rotor" and "Bucking Bronco" are taken from [Dewdney88], but it seems likely to us that the names were reversed in publication, as it is the "Rotor" which bucks, and it is the "Bucking Bronco" which rotates.
See [Langton86], p. 129. Langton uses a normalized Sparseness parameter which he calls parameter
.
Relative to my description,
= 1 - (20 × Sparseness / 255).
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 JC 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. JC freaks can eternally sop up whatever the chipsters
have ready.
A VGA color is specified by giving a six-bit intensity (number between 0 and 63) for each of the primary colors Red, Green and Blue. This makes 18 bits of color, and 218 is 256K. But keep in mind that only 256 different colors are ever on the screen at one time.
Although a pattern would seem to take 320×200×1 byte/pixel = 64,000 bytes, a data compression scheme is used to make the files smaller. The trick is that "runs" of identical cells are written as a count followed by the state of those cells. The values of the counts and of the states are stored as binary integers. You can override the pattern-saving algorithm in two ways--by prefixing the save-file's name with a "!" to save the pattern as an ASCII file, or by prefixing the save-file's name with a "*" to save it as an uncompressed file.
What does this mean? Suppose, for instance that you load the pattern RAT.JCP and try saving it each of the three different ways. (In the days when CelLab was written, the rat was by way of being a corporate mascot of Autodesk, Inc., whose fanatic employees were sometimes called "the hungry rats of Sausalito". To make our rat picture really look really good, you might load the Rat colorpalette RAT.JCC while you look at it.) If you press Ctrl-F4 and save the pattern as "rat" (as was originally done), you get a file RAT.JCP which takes 8422 bytes. If you press Ctrl-F4 and respond "!rat" when JC prompts for the name of the file, then the picture will be saved in ASCII format as RAT.JCP, a file of size 16225 bytes. If you press Ctrl-F4 and respond "*rat" when JC prompts for the name of the file, then the picture will be saved in "uncompressed" format as RATN.JCP, a file of size 64,403 bytes. If you want to compare the three, you actually ought to save them as rat, !rata, and *ratn.
Why would anyone ever save the pattern in anything other than compressed format? Loading an uncompressed pattern is a bit faster, and if your pattern is already so complex that compression only knocks it down to 40 or 50K, then you might consider saving the pattern in uncompressed format, particularly if you are going to use it as part of a demo. But what about an ASCII save? If you use your word processor and look at the ASCII saved RATA.JCP, you'll see that it is saved in compressed format, but that the numbers describing the compression are in standard, readable ASCII characters. RATA.JCP reads "*526,0 1,52 1,4D 317,0..." The asterisk is just a start indicator, and the rest of the characters mean, "Set 526 pixels to state 0, then one pixel to state 52, then one pixel to state 4D, then 317 pixels to state 0,...." The counts are given in decimal, and the color numbers are in hexadecimal. This probably seems perverted, but the reasoning is that it's natural to count things in decimal, but the states from 0 to 255 are best specified as the two-digit hexadecimal numbers 00--FF. Another reason for giving the states in hexadecimal is that it is easy to go back and forth between hexadecimal numbers and binary bit patterns, and our states are, first and foremost, bit patterns saying which of the cell's eight bitplanes are turned on. For more info, see FileForm.DOC in the JC directory.
VGA colors are specified in the CNS color system described by Toby Berk, Lee Brownston, and Arie Kaufman in "A New Color-Naming System for Graphics Languages", IEEE Computer Graphics and Applications, May 1982, p. 37.
A color is specified in the CNS system by a sequence of English words. CNS colors may be achromatic (grey scale values) or chromatic. Chromatic colors consist of a hue (dominant spectral component), saturation (the extent of dilution with white), and lightness (intensity). A chromatic hue is composed by naming and mixing the following primary hues:
Red, Orange/Brown, Yellow, Green, Blue, Purple
and secondary hues:
Reddish, Orangish/Brownish, Yellowish, Greenish, Bluish, Purplish
To obtain one of the primary hues, just specify its name, e.g. "Yellow". To obtain a hue halfway between two primary hues, compose the two bounding hues: for example "Yellow-green" (or "Green-yellow"; it doesn't matter which is specified first). To obtain a hue one quarter the distance from one color to an adjacent color, compose the "ish" form of the adjacent color with the primary color. For example, the hues between Yellow and Green are named:
Yellow
Greenish yellow
Yellow-green (or Green-yellow)
Yellowish green
Green
Brown is a somewhat confusing special case. The color we perceive as brown has the same hue as orange but when seen with reduced saturation and intensity it appears as brown, a color distinct from orange (that's why there's no brown in the rainbow, in case you've ever lost sleep pondering that fact). To compensate for this perceptual quirk, "brown" and "brownish" may be used as synonyms for "orange" and "orangish" when specifying hues. If "brown" or "brownish" are used, the default saturation and lightness (see below) are set so the orange hue appears brown; if explicit saturation and lightness are given orange and brown are synonymous.
Lightness (brightness or intensity) may be specified by adding one of the following adjectives to the color name:
very dark
dark
medium
light
very light
If no lightness adjective appears, a default is assumed (unless a brown hue was named, in which case the default will be "light"). This diverges from the CNS specification in which omitted lightness defaults to medium intensity.
Saturation (the degree of admixture of white light) is specified by the following adjectives:
grayish (or greyish)
moderate
strong
vivid
"Vivid" denotes a fully saturated color, and is the default (unless a brown is specified, in which case the default saturation is "strong").
Examples of chromatic color specifications are:
red
blue-green
purplish red
very dark green
strong yellow-green
very light grayish greenish yellow
the last describing the color of snow I don't recommend you eat.
Achromatic specifications describe 7 shades of grey, to wit:
black
very dark gray
dark gray
gray (or medium gray)
light gray
very light gray
white
in all cases "grey" may be used instead of "gray".
Although the word order used herein is as prescribed by the formal specification of CNS, our implementation is totally insensitive to word order. You can specify "yellow greyish light greenish very" if you like, silly seems how notwithstanding it.
The compression scheme is similar to that used for pattern saves. In compressed form, a run of, say, 135 successive zeroes in the lookup table is represented by the pair 135,0. Full information about the CelLab file formats is in FileForm.DOC in the JC directory.
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 Pascal, (A - B) MOD 2 can return the negative value -1, which will upset the CaMake unit, 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 Sierpinski 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 Waclaw Sierpinski, 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.
This simulator is still available from Cell Systems, 1955 S. Beverly Glen Blvd., Los Angeles, CA 90025, USA. Like me, Platt is a science fiction writer in addition to being a CA hacker.
[Margolus&Toffoli87], pp. 41-42 and pp. 70-71.
[Margolus&Toffoli87], pp. 72-75. RC uses a different source of randomness: the present time in hundredths of a second is used as an offset into program code. JC adjoins this process to the use of 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:
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 CelLab 3D movie Parity shows a three-dimensional version of the Fredkin rule, and the JC rule FredMem is the Parity rule with seven bits of memory. If you use the colorpalette 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]. If you want to quickly sample a large range of one-dimensional CAs, run the program SOUNDCA.EXE which is included in the CelLab RC directory. If the noise annoys, you can silence it by pressing s.
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 on the CelLab disks, the Freestyle CA disk is now obsolete and unavailable.