Log in

No account? Create an account

Codd's Self-Replicating Computer

« previous entry | next entry »
Mar. 10th, 2010 | 06:25 pm

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:
"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.

Link | Leave a comment |

Comments {2}


(no subject)

from: rickbot
date: Mar. 12th, 2010 03:03 am (UTC)

This is pretty awesome, ferglau. It sounds like you had great fun unearthing the old idea and getting it started again, and the beer story is a nice touch.

Have you been waiting years for something like hashlife to exist so you could test Codd's ideas, or was it just a eureka moment when you spotted the potential?

Reply | Thread

Tim Hutton

(no subject)

from: ferkeltongs
date: Mar. 12th, 2010 02:33 pm (UTC)

Thanks! Talking about Codd and beer: I was reading recently that the word "codswallop" is possibly derived from a particular type of glass bottle invented by another chap called Codd and the fact that it was used to store "wallop" or "beer". I think that's all the Codd beer facts I have for you today.

Golly's hashlife implementation (specifically the adaptation of hashlife to multiple state CA) has really opened up a lot of doors for exploring these old CA. There was a flurry of work recently on von Neumann's CA [1] and even more recently on a universal computer/constructor in the Game of Life itself: [2][3]. I'm working on a CA from 1986 at the moment. I should write about how we got John Devore's 1973 design working too. We seem to be in an interesting anachronistic moment when new technology finally catches up with old ideas.

Intellectually of course it's a dead end (we're not learning anything new) but it provides great educational resources for showing the development of the field of artificial life so it's definitely worth doing.

Reply | Thread