Stats for nerds
3recommend
8mentions
4people
2010–2023years
38% recommend63% neutral
Mentions per year
What Hacker News says
- Toffoli[0] & Margolus’[1] Cellular Automata Machines (1987) is the CA bible, I guess. Andrew Adamatsky edited the encyclopedic Cellular Automata (2018). Ed Fredkin's[2] stuff on reversible CA is fascinating. Gerard Vichniac[3] wrote some great papers in the 80s, e.g. Simulating Physics with Cellular Automata (1984). Kenichi Morita[4] papers. Rudy Rucker[5] has written a lot of stuff on 1 and 2D CA, and worked as a CA programmer. Etc. There are a lot of papers. The very common finite element method of solving differential equations and PDEs is basically the same thing as CA - see e.g. Anderson's Computational Fluid Dynamics.
Attractors and approximations for lattice dynamical systems by Shengfan Zhou, 2002.
1954's Studies of Nonlinear Problems by Fermi, Ulam, Pasta, featuring a 1D CA. https://www.cs.princeton.edu/courses/archive/fall02/cs323/li...
Noether's theorem comes up frequently - that every symmetry of the system corresponds to a conservation law.[6]
Smooth Life is Stephan Rafler's very cool version of CGOL with every discrete aspect turned into a continuous one.[7]
[0] https://en.wikipedia.org/wiki/Tommaso_Toffoli
[1] https://people.csail.mit.edu/nhm/ https://en.wikipedia.org/wiki/Norman_Margolus
[2] https://en.wikipedia.org/wiki/Edward_Fredkin
[3] https://scholar.google.com.au/scholar?as_vis=1&hl=en&q=gerar...
[4] https://scholar.google.com/citations?user=kujUxFYAAAAJ&hl=en
[5] https://en.wikipedia.org/wiki/Rudy_Rucker
[6] https://en.wikipedia.org/wiki/Noether%27s_theorem
[7] best video of SmoothLife https://www.youtube.com/watch?v=KJe9H6qS82I
https://sourceforge.net/projects/smoothlife/files/
This slideshow by Rafler contains the best, most complete explanation of it I've found: https://www.youtube.com/watch?v=iyTIXRhjXII
Shadertoy version https://www.shadertoy.com/view/XtdSDn
- Cellular Automata Machines by Toffoli and Margolus. Somewhere over 30 years ago now.
- Reposting a dead post which should not have been dead, from abecedarius:
These had high I-want-to-read-itosity, I thought: Abelson and diSessa, Turtle Geometry Abelson and Sussman, Structure and Interpretation of Computer Programs Aho and Weinberger and Kernighan, The AWK Programming Language Andrew Appel, Compiling With Continuations Jon Bentley, More Programming Pearls Jon Bentley, Programming Pearls Leo Brodie, Thinking FORTH W. H. Burge, Recursive Programming Techniques Carriero and Gelernter, How to Write Parallel Programs A. K. Dewdney, The New Turing Omnibus Edsger Dijkstra, A Discipline of Programming Richard Feynman, The Feynman Lectures on Computation Friedman and Felleisen, The Little Schemer Friedman and Wand and Haynes, Essentials of Programming Languages [1st edition] James F. Gimpel, Algorithms in Snobol4 Paul Graham, On Lisp Philip Greenspun, Philip and Alex's Guide to Web Publishing Grune and Jacobs, Parsing Techniques: A Practical Guide Daniel Hillis, The Connection Machine Kernighan and Pike, The Practice of Programming Kernighan and Pike, The Unix Programming Environment Kernighan and Plauger, Software Tools in Pascal Donald Knuth, Literate Programming Glenn Krasner (editor), Smalltalk-80: Bits of History, Words of Advice Susan Lammers, Programmers at Work Wm Leler, Constraint Programming Languages Liskov and Guttag, Abstraction and Specification in Program Development Peter Norvig, Paradigms of Artificial Intelligence Programming Chris Okasaki, Purely Functional Data Structures Richard O'Keefe, The Craft of Prolog P. J. Plauger, Programming on Purpose I. (and II and III) P. J. Plauger, The Standard C Library Jef Raskin, The Humane Interface Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach Toby Segaran, Programming Collective Intelligence Toffoli and Margolus, Cellular Automata Machines Niklaus Wirth, Project Oberon: The Design of an Operating System and Compiler Witten, Moffat, & Bell, Managing Gigabytes (mostly from my old list at http://wry.me/~darius/personal/books.html) - I really wanted one of those! I held one in my hands one time when I was visiting the MIT-AI Lab -- it was Norman Margolus's, who made the CAM-6 with Tommaso Toffoli, which was programmed in Forth. He wouldn't let me have it, but he let my friend and I borrow a CAM-6 for a weekend science fiction convention to trip out on.
https://news.ycombinator.com/item?id=8860786
https://news.ycombinator.com/item?id=14469113
https://news.ycombinator.com/item?id=34561910
Rudy Rucker writes about his CAM-6 in the CelLab manual:
http://www.fourmilab.ch/cellab/manual/chap5.html
Computer science is still so new that many of the people at the cutting edge have come from other fields. Though Toffoli holds degrees in physics and computer science, Bennett's Ph.D. is in physical chemistry. And twenty-nine year old Margolus is still a graduate student in physics, his dissertation delayed by the work of inventing, with Toffoli, the CAM-6 Cellular Automaton Machine.
After watching the CAM in operation at Margolus's office, I am sure the thing will be a hit. Just as the Moog synthesizer changed the sound of music, cellular automata will change the look of video.
I tell this to Toffoli and Margolus, and they look unconcerned. What they care most deeply about is science, about Edward Fredkin's vision of explaining the world in terms of cellular automata and information mechanics. Margolus talks about computer hackers, and how a successful program is called “a good hack.” As the unbelievably bizarre cellular automata images flash by on his screen, Margolus leans back in his chair and smiles slyly. And then he tells me his conception of the world we live in.
“The universe is a good hack.”
[...]
Margolus and Toffoli's CAM-6 board was finally coming into production around then, and I got the Department to order one. The company making the boards was Systems Concepts of San Francisco; I think they cost $1500. We put our order in, and I started phoning Systems Concepts up and asking them when I was going to get my board. By then I'd gotten a copy of Margolus and Toffoli's book, Cellular Automata Machines, and I was itching to start playing with the board. And still it didn't come. Finally I told System Concepts that SJSU was going to have to cancel the purchase order. The next week they sent the board. By now it was August, 1987.
The packaging of the board was kind of incredible. It came naked, all by itself, in a plastic bag in a small box of styrofoam peanuts. No cables, no software, no documentation. Just a three inch by twelve inch rectangle of plastic—actually two rectangles one on top of the other—completely covered with computer chips. There were two sockets at one end. I called Systems Concepts again, and they sent me a few pages of documentation. You were supposed to put a cable running your graphics card's output into the CAM-6 board, and then plug your monitor cable into the CAM-6's other socket. No, Systems Concepts didn't have any cables, they were waiting for a special kind of cable from Asia. So Steve Ware, one of the SJSU Math&CS Department techs, made me a cable. All I needed then was the software to drive the board, and as soon as I phoned Toffoli he sent me a copy.
Starting to write programs for the CAM-6 took a little bit of time because the language it uses is Forth. This is an offbeat computer language that uses reverse Polish notation. Once you get used to it, Forth is very clean and nice, but it makes you worry about things you shouldn't really have to worry about. But, hey, if I needed to know Forth to see cellular automata, then by God I'd know Forth. I picked it up fast and spent the next four or five months hacking the CAM-6.
The big turning point came in October, when I was invited to Hackers 3.0, the 1987 edition of the great annual Hackers' conference held at a camp near Saratoga, CA. I got invited thanks to James Blinn, a graphics wizard who also happens to be a fan of my science fiction books. As a relative novice to computing, I felt a little diffident showing up at Hackers, but everyone there was really nice. It was like, “Come on in! The more the merrier! We're having fun, yeeeeee-haw!”
I brought my AT along with the CAM-6 in it, and did demos all night long. People were blown away by the images, though not too many of them sounded like they were ready to a) cough up $1500, b) beg Systems Concepts for delivery, and c) learn Forth in order to use a CAM-6 themselves. A bunch of the hackers made me take the board out of my computer and let them look at it. Not knowing too much about hardware, I'd imagined all along that the CAM-6 had some special processors on it. But the hackers informed me that all it really had was a few latches and a lot of fast RAM memory chips.
- I mentioned and quoted Rudy's wonderful work with the CAM6, which also inspired me a lot, in this discussion:
https://news.ycombinator.com/item?id=14468834
Rudy Rucker writes about his CAM-6 in the CelLab manual:
http://www.fourmilab.ch/cellab/manual/chap5.html
Computer science is still so new that many of the people at the cutting edge have come from other fields. Though Toffoli holds degrees in physics and computer science, Bennett's Ph.D. is in physical chemistry. And twenty-nine year old Margolus is still a graduate student in physics, his dissertation delayed by the work of inventing, with Toffoli, the CAM-6 Cellular Automaton Machine.
After watching the CAM in operation at Margolus's office, I am sure the thing will be a hit. Just as the Moog synthesizer changed the sound of music, cellular automata will change the look of video.
I tell this to Toffoli and Margolus, and they look unconcerned. What they care most deeply about is science, about Edward Fredkin's vision of explaining the world in terms of cellular automata and information mechanics. Margolus talks about computer hackers, and how a successful program is called “a good hack.” As the unbelievably bizarre cellular automata images flash by on his screen, Margolus leans back in his chair and smiles slyly. And then he tells me his conception of the world we live in.
“The universe is a good hack.”
[...]
Margolus and Toffoli's CAM-6 board was finally coming into production around then, and I got the Department to order one. The company making the boards was Systems Concepts of San Francisco; I think they cost $1500. We put our order in, and I started phoning Systems Concepts up and asking them when I was going to get my board. By then I'd gotten a copy of Margolus and Toffoli's book, Cellular Automata Machines, and I was itching to start playing with the board. And still it didn't come. Finally I told System Concepts that SJSU was going to have to cancel the purchase order. The next week they sent the board. By now it was August, 1987.
The packaging of the board was kind of incredible. It came naked, all by itself, in a plastic bag in a small box of styrofoam peanuts. No cables, no software, no documentation. Just a three inch by twelve inch rectangle of plastic—actually two rectangles one on top of the other—completely covered with computer chips. There were two sockets at one end. I called Systems Concepts again, and they sent me a few pages of documentation. You were supposed to put a cable running your graphics card's output into the CAM-6 board, and then plug your monitor cable into the CAM-6's other socket. No, Systems Concepts didn't have any cables, they were waiting for a special kind of cable from Asia. So Steve Ware, one of the SJSU Math&CS Department techs, made me a cable. All I needed then was the software to drive the board, and as soon as I phoned Toffoli he sent me a copy.
Starting to write programs for the CAM-6 took a little bit of time because the language it uses is Forth. This is an offbeat computer language that uses reverse Polish notation. Once you get used to it, Forth is very clean and nice, but it makes you worry about things you shouldn't really have to worry about. But, hey, if I needed to know Forth to see cellular automata, then by God I'd know Forth. I picked it up fast and spent the next four or five months hacking the CAM-6.
The big turning point came in October, when I was invited to Hackers 3.0, the 1987 edition of the great annual Hackers' conference held at a camp near Saratoga, CA. I got invited thanks to James Blinn, a graphics wizard who also happens to be a fan of my science fiction books. As a relative novice to computing, I felt a little diffident showing up at Hackers, but everyone there was really nice. It was like, “Come on in! The more the merrier! We're having fun, yeeeeee-haw!”
I brought my AT along with the CAM-6 in it, and did demos all night long. People were blown away by the images, though not too many of them sounded like they were ready to a) cough up $1500, b) beg Systems Concepts for delivery, and c) learn Forth in order to use a CAM-6 themselves. A bunch of the hackers made me take the board out of my computer and let them look at it. Not knowing too much about hardware, I'd imagined all along that the CAM-6 had some special processors on it. But the hackers informed me that all it really had was a few latches and a lot of fast RAM memory chips.
- Here's another ecology oriented cellular automata rule called ECOLIBRA, a cross between LIFE, BRAIN (and optionally ANNEAL on the bit plane that determines water/land), from John Walker's and Rudy Rucker's classic CelLab (which Autodesk originally published as a PC application, but John Walker has ported to JavaScript):
https://www.fourmilab.ch/cellab/manual/rules.html#EcoLiBra
>ECOLIBRA
>This rule is a cross between Life and Brain. The basic idea is that the cells are divided between dark “sea” cells and light “land” cells. We run Brain in the sea, and on land we run not Life but AntiLife. All the land cells are normally firing cells, and the presence of an active AntiLife cell is signaled by having a land cell which is not firing. Full details on EcoLiBra are in the Cellular Automata Theory chapter.
>The name EcoLiBra suggests 1) an ecology of Life and Brain, 2) a balanced situation (equilibrium), and 3) the human intestinal bacteria Escherichia coli, known as E. coli for short. The third connection is perhaps a bit unsavory, but remember that E. coli cells are in fact the favorite “guinea pigs” for present day gene splicing experiments. As one of the goals of CelLab is to promote the development of artificial life, the designer gene connection is entirely appropriate. I've given EcoLiBra a nice, symmetric start pattern, but it also does fine if you use the Bit Plane Editor to randomize all bit planes.
https://www.fourmilab.ch/cellab/manual/chap4.html#EcoLiBra
>The EcoLiBra rule, consisting of Brain and AntiLife, each turned on by the red/black boundary.
>But when the sea runs Brain and the land runs Life, the situation is no longer symmetrical. The pervasive presence of Brain's refractory state makes it less likely for a sea cell to have seven firing neighbors and be turned into a land cell. Unless we change the transition rules, the land will always melt away. So to give land a fighting chance, I now say that a sea cell becomes land if it has seven or six firing neighbors. Also I use better colors: Black, blue, and green for Brain; red and yellow for AntiLife.
Here is a variant I call "ECO" that runs "ANNEAL" on the water/land plane, and (for giggles) a heat diffusion in the upper left-over planes.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Here are the guts of the rule (omitting the heat diffusion layer calculation):
The CelLab user's guide and Rudy Rucker's recounting of the origins of CelLab and his experience with Margolus and Toffoli's CAM6 is especially delightful.var cell = 0; var sum9Anneal = ((nw & 0x04) + (n & 0x04) + (ne & 0x04) + (w & 0x04) + (c & 0x04) + (e & 0x04) + (sw & 0x04) + (s & 0x04) + (se & 0x04)) >> 2; var anneal = ((sum9Anneal > 5) || (sum9Anneal == 4)) ? 4 : 0; cell |= anneal; var sum8 = (nw & 1) + (n & 1) + (ne & 1) + (w & 1) + (e & 1) + (sw & 1) + (s & 1) + (se & 1); if (anneal) { // Anti-Life cell |= ((c & 1) << 1); if (c & 1) { if (sum8 != 5) { cell |= 0x01; } } else { if ((sum8 != 5) && (sum8 != 6)) { cell |= 0x01; } } } else { // Brain cell |= (c << 1) & 2; if ((c & 3) == 0) { if (sum8 == 2) { cell |= 1; } } }https://www.fourmilab.ch/cellab/manual/
https://www.fourmilab.ch/cellab/manual/chap5.html
Bennett shows me another pattern, one that looks like boiling red cottage cheese, and then he takes me across the Charles River to the MIT Laboratory of Computer Science. In the basement is an exuberant French scientist named Gérard Vichniac. He and an associate are watching a small rectangular dot-pattern in the center of their terminal's screen. The pattern is mostly white, with a small amount of red in it. The edges keep folding in on each other as the pattern evolves according to some simple rule which Vichniac made up. He calls it an “Ising Model,” but it looks like an electronic kaleidoscope. “This pattern started as a red square,” Vichniac tells me. “The rule is reversible, so we know that eventually the red square must come back. We've been watching it for eighty thousand steps now”.
Upstairs from Vichniac are two equally cheerful cellular automata specialists, Norman Margolus and Tommaso Toffoli. There's another journalist there, a guy from Rolling Stone.[Footnote] Cellular automata are hot. I introduce myself and sit down to watch the demonstration. Right now there's a central cloud of dots, with square little patterns flying out of it. On the sides of each of the square patterns are individual pixels that pump up and down.
“Look at the critters, Tom,” says Margolus. “They look like rowers, don't they?”[Footnote]
“Show him the square rock,” says Toffoli.
Margolus clears the screen and keys a big red square into the center. The square expands out to the edges of the screen and bounces back. As the bouncing continues, the patterns interfere and form complex checkerboard patterns, enough patterns in thirty seconds to have made a respectable one-man Op-Art show in the 1960s.
Toffoli pries Margolus away from the controls and takes over. “Now we do the square rock in the toroidal pond again, but this time we add a heat-bath, a cloud of random gas in the background.”
The background fills with darting dots, and Toffoli keys another big red square into the center. This time the waves are smooth and roughly circular, much like real waves in a real pond. We try it with two squares and get interference patterns. Toffoli is pleased. He says that this shows how simple physics really is.
[...]
After watching the CAM in operation at Margolus's office, I am sure the thing will be a hit. Just as the Moog synthesizer changed the sound of music, cellular automata will change the look of video.
I tell this to Toffoli and Margolus, and they look unconcerned. What they care most deeply about is science, about Edward Fredkin's vision of explaining the world in terms of cellular automata and information mechanics. Margolus talks about computer hackers, and how a successful program is called “a good hack.” As the unbelievably bizarre cellular automata images flash by on his screen, Margolus leans back in his chair and smiles slyly. And then he tells me his conception of the world we live in.
“The universe is a good hack.”
[...]
Margolus and Toffoli's CAM-6 board was finally coming into production around then, and I got the Department to order one. The company making the boards was Systems Concepts of San Francisco; I think they cost $1500. We put our order in, and I started phoning Systems Concepts up and asking them when I was going to get my board. By then I'd gotten a copy of Margolus and Toffoli's book, Cellular Automata Machines, and I was itching to start playing with the board. And still it didn't come. Finally I told System Concepts that SJSU was going to have to cancel the purchase order. The next week they sent the board. By now it was August, 1987.
The packaging of the board was kind of incredible. It came naked, all by itself, in a plastic bag in a small box of styrofoam peanuts. No cables, no software, no documentation. Just a three inch by twelve inch rectangle of plastic—actually two rectangles one on top of the other—completely covered with computer chips. There were two sockets at one end. I called Systems Concepts again, and they sent me a few pages of documentation. You were supposed to put a cable running your graphics card's output into the CAM-6 board, and then plug your monitor cable into the CAM-6's other socket. No, Systems Concepts didn't have any cables, they were waiting for a special kind of cable from Asia. So Steve Ware, one of the SJSU Math&CS Department techs, made me a cable. All I needed then was the software to drive the board, and as soon as I phoned Toffoli he sent me a copy.
Starting to write programs for the CAM-6 took a little bit of time because the language it uses is Forth. This is an offbeat computer language that uses reverse Polish notation. Once you get used to it, Forth is very clean and nice, but it makes you worry about things you shouldn't really have to worry about. But, hey, if I needed to know Forth to see cellular automata, then by God I'd know Forth. I picked it up fast and spent the next four or five months hacking the CAM-6.
Related
Algorithms in SNOBOL4
2 recommend · 3
Cellular automata
3 recommend · 7
Introduction to automata theory, languages, and computation
24 recommend · 37
Cellular automata and complexity
1 recommend · 3
Paradigms of Artificial Intelligence
63 recommend · 169
An introduction to formal languages and automata
4 recommend · 5
