The Wikipedia article discusses and cites the paper, but the link is broken, so here's a better one:
"Signal crossing solutions in von Neumann self-replicating cellular automata", page 453-503
https://donhopkins.com/home/documents/automata2008reducedsiz...
It has a great nuts-and-bolts explanation of how John von Neumann's 29 state rule and his universal constructor work, with lots of details, theories, and practical advice about the design and working of various "organs", like basic building blocks (specifically signal crossings), reusable components, higher level machines, programming techniques, data representation and coding, and overall architecture.
The paper is about how to construct organs that initialize themselves the first time they come alive, kind of like a C++ constructor, that's only used once in the lifetime of an object.
That's important because you have to construct unexcited devices with the power off (no excited states), using a construction arm kind of like a 3d or ink jet printer head, but 2d and cells, driven by a "tape" of instructions that moves the arm back and forth and draws the required 2d grid of cells.
Factorio players will recognize these tapes of construction instructions as 2D "blueprints" that construction drones use to build patterns of factories and conveyor belts, etc. In Factorio, after your drones have build a blueprint in the unpowered, unsupplied state, you can connect it to the power grid, hook up pipes to deliver fluids, and run conveyor belts in and out of it to deliver resources and products, and it will immediately starts doing its thing. Playing Factorio is uncannily like von Neumann 29 state cellular automata programming, not by coincidence. So it's a great way to get your head around cellular automata programming, gpu programming, parallel programming, queuing systems, and data flow programming in general!
Factorio Tutorial #20 - Bots, part 1 - Construction robots
https://www.youtube.com/watch?v=kLOyk55uI2Y&t=19m32s
Factorio just doesn't have the ability to construct cells by spilling items off the end of conveyor belts, or destroy cells with conveyor belts, either. But maybe there's an extension for that! And John von Neumann's 29 state cellular automata doesn't have swarms of construction drones that build and tear down blueprints in parallel like Factorio does, so there are some differences. But the basic idea of grids of cells with conveyor belts carrying items between factories is the same.
Once you construct an auto-initializing machine, you inject the powered-off copy with a signal, like a reset pulse followed by data, for it to process. And the data can be a program like a series of instructions to control the drawing arm, data to transfer or process, timing signals, or control signals for other machines.
Not all machines need to auto-initialize, but machines that use auto-initialization "code" run it once first to set up all the timers and signals, and then the code cuts itself off and switches to the normal runtime "code" for processing the input signals, using "self modifying code" that cuts the traces to the initialization circuit and draws the traces to conduct the signal into the now-initialized machine itself.
(Self modifying code can destroy an arrow by pointing to it with another "special" kind of arrow, and sending an excited signal to it, then it disappears and cuts off the downstream circuit. And it can draw new arrows at any time, the same way as the construction arm does, by pointing an arrow at an empty unexcited space, and sending out a series of on/off signals to select which cell to create (huffman encoding).
So the construction arm prints out an unpowered machine, which, when powered up, initializes itself once, and then modifies itself to permanently switch into run mode.
A self replicating machine (which was stupendously huge and complex for a program from 1940 designed on graph paper without the help of computers, but is a microscopic speck compared to Electron today) first prints a powered-down copy of itself, then injects a copy of its program into the storage device of the new copy through an "umbilical cord", then sends it a reset signal to boot it to "life" and make it start executing its copy of the program from its own tape, and reproducing itself. (Breathing a copy of its "soul" into its new child machine, so to speak.)
The parent would typically print a copy of itself offset in the same direction as its parent had printed it, then shut down (or at least stop building and go into a deep state of meditation, counting electric sheep or something) after reproducing once, so as not to hurt its child. It's left as an exercise to the reader to design a self reproducing machine that knows how to eat its parent to make more room to expand, but it's probably impossible to design a machine that could destroy itself.
For one of the best and most beautiful books on cellular automata in general, check out Margolus and Toffoli's "Cellular Automata Machines: A New Environment for Modeling" from MIT Press, which describes the CAM-6 hardware:
https://www.amazon.com/Cellular-Automata-Machines-Environmen...
https://donhopkins.com/home/Tommaso_Toffoli_Norman_Margolus_...
(by permission of the authors)
CAM-6 Forth source code:
http://www.donhopkins.com/home/code/tomt-cam-forth-scr.txt
http://www.donhopkins.com/home/code/tomt-users-forth-scr.txt
Rudy Rucker has also written some wonderful stuff about the CAM-6:
https://news.ycombinator.com/item?id=14469113
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.
DonHopkins on March 31, 2020 | parent | context | favorite | on: Von Neumann Universal Constructor
Check out Buckley's paper, "Signal crossing solutions in von Neumann self-replicating cellular automata", page 453-503 of the Automata-2008 proceedings. The Wikipedia article discusses and cites the paper, but the link is broken, so here's a better one:
"Signal crossing solutions in von Neumann self-replicating cellular automata", page 453-503
https://donhopkins.com/home/documents/automata2008reducedsiz...
It has a great nuts-and-bolts explanation of how John von Neumann's 29 state rule and his universal constructor work, with lots of details, theories, and practical advice about the design and working of various "organs", like basic building blocks (specifically signal crossings), reusable components, higher level machines, programming techniques, data representation and coding, and overall architecture.
The paper is about how to construct organs that initialize themselves the first time they come alive, kind of like a C++ constructor, that's only used once in the lifetime of an object.
That's important because you have to construct unexcited devices with the power off (no excited states), using a construction arm kind of like a 3d or ink jet printer head, but 2d and cells, driven by a "tape" of instructions that moves the arm back and forth and draws the required 2d grid of cells.
Factorio players will recognize these tapes of construction instructions as 2D "blueprints" that construction drones use to build patterns of factories and conveyor belts, etc. In Factorio, after your drones have build a blueprint in the unpowered, unsupplied state, you can connect it to the power grid, hook up pipes to deliver fluids, and run conveyor belts in and out of it to deliver resources and products, and it will immediately starts doing its thing. Playing Factorio is uncannily like von Neumann 29 state cellular automata programming, not by coincidence. So it's a great way to get your head around cellular automata programming, gpu programming, parallel programming, queuing systems, and data flow programming in general!
Factorio Tutorial #20 - Bots, part 1 - Construction robots
https://www.youtube.com/watch?v=kLOyk55uI2Y&t=19m32s
Factorio just doesn't have the ability to construct cells by spilling items off the end of conveyor belts, or destroy cells with conveyor belts, either. But maybe there's an extension for that! And John von Neumann's 29 state cellular automata doesn't have swarms of construction drones that build and tear down blueprints in parallel like Factorio does, so there are some differences. But the basic idea of grids of cells with conveyor belts carrying items between factories is the same.
Once you construct an auto-initializing machine, you inject the powered-off copy with a signal, like a reset pulse followed by data, for it to process. And the data can be a program like a series of instructions to control the drawing arm, data to transfer or process, timing signals, or control signals for other machines.
Not all machines need to auto-initialize, but machines that use auto-initialization "code" run it once first to set up all the timers and signals, and then the code cuts itself off and switches to the normal runtime "code" for processing the input signals, using "self modifying code" that cuts the traces to the initialization circuit and draws the traces to conduct the signal into the now-initialized machine itself.
(Self modifying code can destroy an arrow by pointing to it with another "special" kind of arrow, and sending an excited signal to it, then it disappears and cuts off the downstream circuit. And it can draw new arrows at any time, the same way as the construction arm does, by pointing an arrow at an empty unexcited space, and sending out a series of on/off signals to select which cell to create (huffman encoding).
So the construction arm prints out an unpowered machine, which, when powered up, initializes itself once, and then modifies itself to permanently switch into run mode.
A self replicating machine (which was stupendously huge and complex for a program from 1940 designed on graph paper without the help of computers, but is a microscopic speck compared to Electron today) first prints a powered-down copy of itself, then injects a copy of its program into the storage device of the new copy through an "umbilical cord", then sends it a reset signal to boot it to "life" and make it start executing its copy of the program from its own tape, and reproducing itself. (Breathing a copy of its "soul" into its new child machine, so to speak.)
The parent would typically print a copy of itself offset in the same direction as its parent had printed it, then shut down (or at least stop building and go into a deep state of meditation, counting electric sheep or something) after reproducing once, so as not to hurt its child.
It's left as an exercise to the reader to design a self reproducing machine that knows how to eat its parent to make more room to expand, or a parent that eats its children, but it's probably impossible to design a machine that could destroy itself (like "delete this" in C++). Deleting that last little part would be tricky!
https://www.youtube.com/watch?v=tJBeih6JZrs
For one of the best and most beautiful books on cellular automata in general, check out Margolus and Toffoli's "Cellular Automata Machines: A New Environment for Modeling" from MIT Press, which describes the CAM-6 hardware:
https://www.amazon.com/Cellular-Automata-Machines-Environmen...
https://donhopkins.com/home/Tommaso_Toffoli_Norman_Margolus_...
(by permission of the authors)
CAM-6 Forth source code:
http://www.donhopkins.com/home/code/tomt-cam-forth-scr.txt
http://www.donhopkins.com/home/code/tomt-users-forth-scr.txt
Rudy Rucker has also written some wonderful stuff about the CAM-6:
https://news.ycombinator.com/item?id=14469113
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.