Codd's Self-Replicating Computer
My paper on Edgar F. Codd's self-replicating computer is out today: [official link][preprint PDF]
It's one of the strangest papers I've ever written. It's published in Artificial Life but I considered sending it to IEEE Annals of Computing History because, well, basically the paper is 40 years late. Sorry about that.
The paper is about a cellular automata design from 1968, pointing out that there are (very minor) problems with the design and showing how to correct them. The solution and the resulting implementation are expected to be of interest to virtually nobody since there are now known to be far better ways of achieving what Codd was suggesting. There is some historical interest but only because many later self-replicators inherited Codd's ideas and this paper tidies up some loose ends.
The one redeeming feature of the paper is that implementation hasn't really been possible until the last year or two because it relies on a very recent software development: Golly's hashlife. This is because the machine is too damn big. Here are some images to show you what I mean.
Here's the main body of the machine. It's 56,000 cells high.
Here's a zoom-in on part of the main body:
You can't see the components yet because we've still got a long way to zoom-in. Here's an animated gif that takes you on a quick tour of the machine in action:
(I'm not very good at stop-motion animation, as you can see.)
And the amazing thing about Golly is that even though the machine has 284 million cells, Golly manages to run it at 50 million iterations per second, even on a single desktop PC. Even at that speed it would take 1000 years for the machine to replicate fully. I've put some more details about how Codd's machine works here.
Codd himself died in 2003. He would probably be appalled that someone actually implemented his machine, because his work (it was his PhD thesis) was basically an existence proof, not a practical suggestion. It's even reported that it started over a bet in a pub:
It has been an enormous amount of fun getting it to work. A bit like putting an engine together, you don't really know if it's going to actually work until the last moment when you actually turn it on.
It's one of the strangest papers I've ever written. It's published in Artificial Life but I considered sending it to IEEE Annals of Computing History because, well, basically the paper is 40 years late. Sorry about that.
The paper is about a cellular automata design from 1968, pointing out that there are (very minor) problems with the design and showing how to correct them. The solution and the resulting implementation are expected to be of interest to virtually nobody since there are now known to be far better ways of achieving what Codd was suggesting. There is some historical interest but only because many later self-replicators inherited Codd's ideas and this paper tidies up some loose ends.
The one redeeming feature of the paper is that implementation hasn't really been possible until the last year or two because it relies on a very recent software development: Golly's hashlife. This is because the machine is too damn big. Here are some images to show you what I mean.
Here's the main body of the machine. It's 56,000 cells high.
Here's a zoom-in on part of the main body:
You can't see the components yet because we've still got a long way to zoom-in. Here's an animated gif that takes you on a quick tour of the machine in action:
(I'm not very good at stop-motion animation, as you can see.)
And the amazing thing about Golly is that even though the machine has 284 million cells, Golly manages to run it at 50 million iterations per second, even on a single desktop PC. Even at that speed it would take 1000 years for the machine to replicate fully. I've put some more details about how Codd's machine works here.
Codd himself died in 2003. He would probably be appalled that someone actually implemented his machine, because his work (it was his PhD thesis) was basically an existence proof, not a practical suggestion. It's even reported that it started over a bet in a pub:
"Dr. Codd related that he and a fellow doctoral student were in a pub and the "lad was speaking rather reverently of John Von Neumann's 29-state machine." Ted, not one to let something like this slide by (Sharon, you know this wonderful trait so well), insisted he could beat that! Ted boldly said he could drastically reduce the number of required states and still produce the same results. His buddy replied in the negative. With the quick retort, "Yes, I can, I'll bet you I can!" the challenge demanded some sort of "formality." Dr. Codd said to me, "We were poor graduate students, what did we have of value to bet?" "How about a beer?" Ted chuckled over the phone. And, sure enough, shortly thereafter they returned to the pub and Ted presented his eight-state machine (8-state cellular automata).
Ted and I laughed over the fact that a "branch of science," artificial life, was borne from a bet over a beer." -- http://c2.com/cgi/wiki?DrCodd
It has been an enormous amount of fun getting it to work. A bit like putting an engine together, you don't really know if it's going to actually work until the last moment when you actually turn it on.
This post was originally on LiveJournal.