Theory of Self Reproducing Automata (1966) [pdf]
cba.mit.edu
cba.mit.edu
As a Harvard math PhD student around 1980, Fridays were amusing. In the math department was "wine and cheese" and inebriation levels were high by modern standards.
Over in the bio labs, they preferred cannabis. The sessions were intellectually stimulating, with a reverence for when Timothy Leary ran his "seminars". That's where I first saw this book, and it made a lasting impression.
Then they were able to show a construction that was self replicating with great generality because it worked using a sort of Turing machine tape to guide its operations.
DonHopkins on March 31, 2020 | parent | context | favorite | on: Von Neumann Universal Constructor
Here's some stuff about that I posted in an earlier discussion, and transcribed from his book, "Theory of Self-Reproducing Automata".
His concept of self-reproducing mutating probabilistic quantum mechanical machine evolution is quite fascinating and terrifying at the same time (or outside of time), potentially much more powerful and dangerous than mere physical nanotechnology "gray goo" and universe-infesting self replicating von Neumann probes:
Can Programming Be Liberated from the von Neumann Style? (1977) [pdf] (thocp.net)
https://news.ycombinator.com/item?id=21855249
https://news.ycombinator.com/item?id=21858465
John von Neuman's 29 state cellular automata machine is (ironically) a classical decidedly "non von Neumann architecture".
https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton
He wrote the book on "Theory of Self-Reproducing Automata":
https://archive.org/details/theoryofselfrepr00vonn_0
He designed a 29 state cellular automata architecture to implement a universal constructor that could reproduce itself (which he worked out on paper, amazingly):
https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...
He actually philosophized about three different kinds of universal constructors at different levels of reality:
First, the purely deterministic and relatively harmless mathematical kind referenced above, an idealized abstract 29 state cellular automata, which could reproduce itself with a Universal Constructor, but was quite brittle, synchronous, and intolerant of errors. These have been digitally implemented in the real world on modern computing machinery, and they make great virtual pets, kind of like digital tribbles, but not as cute and fuzzy.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Second, the physical mechanical and potentially dangerous kind, which is robust and error tolerant enough to work in the real world (given enough resources), and is now a popular theme in sci-fi: the self reproducing robot swarms called "Von Neumann Probes" on the astronomical scale, or "Gray Goo" on the nanotech scale.
https://en.wikipedia.org/wiki/Self-replicating_spacecraft#Vo...
https://grey-goo.fandom.com/wiki/Von_Neumann_probe
>The von Neumann probe, nicknamed the Goo, was a self-replicating nanomass capable of traversing through keyholes, which are wormholes in space. The probe was named after Hungarian-American scientist John von Neumann, who popularized the idea of self-replicating machines.
Third, the probabilistic quantum mechanical kind, which could mutate and model evolutionary processes, and rip holes in the space-time continuum, which he unfortunately (or fortunately, the the sake of humanity) didn't have time to fully explore before his tragic death.
p. 99 of "Theory of Self-Reproducing Automata":
>Von Neumann had been interested in the applications of probability theory throughout his career; his work on the foundations of quantum mechanics and his theory of games are examples. When he became interested in automata, it was natural for him to apply probability theory here also. The Third Lecture of Part I of the present work is devoted to this subject. His "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" is the first work on probabilistic automata, that is, automata in which the transitions between states are probabilistic rather than deterministic. Whenever he discussed self-reproduction, he mentioned mutations, which are random changes of elements (cf. p. 86 above and Sec. 1.7.4.2 below). In Section 1.1.2.1 above and Section 1.8 below he posed the problems of modeling evolutionary processes in the framework of automata theory, of quantizing natural selection, and of explaining how highly efficient, complex, powerful automata can evolve from inefficient, simple, weak automata. A complete solution to these problems would give us a probabilistic model of self-reproduction and evolution. [9]
[9] For some related work, see J. H. Holland, "Outline for a Logical Theory of Adaptive Systems", and "Concerning Efficient Adaptive Systems".
https://www.deepdyve.com/lp/association-for-computing-machin...
https://deepblue.lib.umich.edu/bitstream/handle/2027.42/5578...
https://www.worldscientific.com/worldscibooks/10.1142/10841
Ericson2314 3 months ago [-]
> Although I refer to conventional languages as "von Neumann languages" to take note of their origin and style, I do not, of course, blame the great mathematician for their complexity. In fact, some might say that I bear some responsibility for that problem.
From the paper. Whew.
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.