A Self-Interpreter for Conway's "Game of Life"
John Horton Conway's "Game of Life" was one of many amazing things Martin Gardner wrote about in his Mathematical Games column in Scientific American a few decades ago. I used to read those columns as a schoolboy in the 70s, and "Life" was something I found totally fascinating back then and have revisited periodically every since. It was probably a significant influence on me eventually heading into a career in computer programming. Back in 1982 I even ended up writing a Z80 assembly language implementation on my trusty TRS-80 Model I. I tried to sell it but the software distributor wasn't interested, claiming they already had several other versions of something similar from others. But I still have a printout of that code somewhere - my one and only significant programming project done all in assembly! (Copies available on request. :-)
Anyway, ever since starting this blog, a thought has been lurking in the back of my mind about the possibility of a self-interpreter for "Life". I imagined this would be a rather large pattern that could be used to tile the entire Life universe, and each such copy of the pattern would (somehow) emulate one cell of Life. If you can work out how to do that, then you can have that emulation run another set of copies of the same pattern, and on, ad infinitum! Something led me back to this again in the last few days and I started trawling the web to see if it had already been done. Although I didn't find anything in that vein, I did find a bunch of other amazing stuff that various people have done in more recent years, including Paul Rendell's construction of a Turing machine in Life. So I decided to contact him to ask if he knew of any existing pattern of the kind I was interested in, and if he had any advice to offer a newbie Life pattern constructor if not. Today I received his reply, pointing me to David Bell's "Unit Cell" pattern, created over ten years ago.
I have to admit to feeling some disappointment, because I'd started to hope that nobody else had thought of this idea and perhaps I could even be the first to construct it. Hah! It actually turned out the pattern was bundled in a collection that comes with Golly, an open source life simulator that I already had on my machine - I just hadn't looked hard enough through all those sample patterns and obviously also hadn't searched for the right terms when using Google! By the way, Golly is amazingly fast - I concede perhaps even a tad quicker than my old Z80 version - but no doubt only because of the super clever Hashlife algorithm it uses! I don't have a full understanding of this algorithm yet but it seems it was invented by Bill Gosper about the same time I was writing my Z80 code. Obviously I was talking to the wrong people back then, although implementing Hashlife in 16K of RAM and in assembler might have been somewhat challenging also!
Dragging myself back on topic again, Life's "Self-Interpreter" has already been created, and it's a thing of beauty. Grab Golly and have a look - in the version 1.2 distribution the pattern is second to last in the Signal-Circuitry group. The pattern below that ("Deep Cell") turns out to be a modified version that actually emulates two independent Life cells at the same time (can't say I've seen that trick in any other self-interpreters!) and a bit more poking around also turned up Brice Due's Metapixel pattern, a more recent and further major development that lets Life emulate a whole class of other cellular automata that use different rules as well as itself. I also want to mention Jason Summers' "unit cell" that emulates Wolfram's Rule 110 which is known to be universal. In fact, there's so much cool stuff in this whole area that I hardly know where to start or end.
But the main point as far as this blog goes is that "Life" has a self-interpreter, and it's eigenratio is exactly 5760! (That's the number of generations that need to be run in Dean Bell's unit cell at level N in order to emulate a single generation in level N+1.) One interesting aspect of this is that the ratio is the same between all levels of any such similar Life "self-interpreter" that you might want to stack on top of each other - rather than just being the limit as the number of levels goes to infinity as in self-interpreters for more conventional computational systems. I'm not quite sure what to think of the corresponding matrix though - I guess it is just a scalar value in this case?
Anyway, I must go and play with Golly again. I can only recommend that you do the same!
Anyway, ever since starting this blog, a thought has been lurking in the back of my mind about the possibility of a self-interpreter for "Life". I imagined this would be a rather large pattern that could be used to tile the entire Life universe, and each such copy of the pattern would (somehow) emulate one cell of Life. If you can work out how to do that, then you can have that emulation run another set of copies of the same pattern, and on, ad infinitum! Something led me back to this again in the last few days and I started trawling the web to see if it had already been done. Although I didn't find anything in that vein, I did find a bunch of other amazing stuff that various people have done in more recent years, including Paul Rendell's construction of a Turing machine in Life. So I decided to contact him to ask if he knew of any existing pattern of the kind I was interested in, and if he had any advice to offer a newbie Life pattern constructor if not. Today I received his reply, pointing me to David Bell's "Unit Cell" pattern, created over ten years ago.
I have to admit to feeling some disappointment, because I'd started to hope that nobody else had thought of this idea and perhaps I could even be the first to construct it. Hah! It actually turned out the pattern was bundled in a collection that comes with Golly, an open source life simulator that I already had on my machine - I just hadn't looked hard enough through all those sample patterns and obviously also hadn't searched for the right terms when using Google! By the way, Golly is amazingly fast - I concede perhaps even a tad quicker than my old Z80 version - but no doubt only because of the super clever Hashlife algorithm it uses! I don't have a full understanding of this algorithm yet but it seems it was invented by Bill Gosper about the same time I was writing my Z80 code. Obviously I was talking to the wrong people back then, although implementing Hashlife in 16K of RAM and in assembler might have been somewhat challenging also!
Dragging myself back on topic again, Life's "Self-Interpreter" has already been created, and it's a thing of beauty. Grab Golly and have a look - in the version 1.2 distribution the pattern is second to last in the Signal-Circuitry group. The pattern below that ("Deep Cell") turns out to be a modified version that actually emulates two independent Life cells at the same time (can't say I've seen that trick in any other self-interpreters!) and a bit more poking around also turned up Brice Due's Metapixel pattern, a more recent and further major development that lets Life emulate a whole class of other cellular automata that use different rules as well as itself. I also want to mention Jason Summers' "unit cell" that emulates Wolfram's Rule 110 which is known to be universal. In fact, there's so much cool stuff in this whole area that I hardly know where to start or end.
But the main point as far as this blog goes is that "Life" has a self-interpreter, and it's eigenratio is exactly 5760! (That's the number of generations that need to be run in Dean Bell's unit cell at level N in order to emulate a single generation in level N+1.) One interesting aspect of this is that the ratio is the same between all levels of any such similar Life "self-interpreter" that you might want to stack on top of each other - rather than just being the limit as the number of levels goes to infinity as in self-interpreters for more conventional computational systems. I'm not quite sure what to think of the corresponding matrix though - I guess it is just a scalar value in this case?
Anyway, I must go and play with Golly again. I can only recommend that you do the same!
posted by Clive at 9:16 pm
3 Comments:
Now this is very cool. I've been thinking all along that low eigenratios aren't interesting; the lower, the less in the way of interesting work the interpreter is doing. "Cheating" by calling 'eval' (eigenratio ~= 1) is merely the extreme end of the continuum.
Eigenratio in the thousands (assuming no deliberate waste of cycles of course) is the indication the Life unit cell is nontrivial; it's doing some interesting work.
(Since there's only one instruction in Life, the matrix would be a 1*1 matrix.)
At that, the Life unit cell is optimized for speed over size (massive parallelism, one core per intepreted cell). You could get it much more compact by using a single core to handle a large chunk of the interpreted plane (represented as e.g. a loop of gliders); the eigenratio in that case could be made arbitrarily high.
Thanks for your comment Russell - and for being interested enough to read my blog in the first place!
Around about the same time that I published this post about Life and so on, I was also in contact with Torben Mogensen and Amir ben-Amram from the University of Copenhagen. I wanted to understand what was already known about the relationship (for some given language) between the property of being Turing-complete and the property of having a self-interpreter. (I'd found their names independently when trawling the Net looking for people who had written or commented about such things, and then found out they are both currently at the same institution!)
Anyway the discussion (with Torben mainly) closed with a brief exchange about Life, self-interpreters for it, Turing completeness and so on. One thing that came out of that for me was the realisation that there is a kind of distinction that perhaps needs to be made. On one hand, you can consider finite initial patterns for Life. These can clearly be emulated on any other Turing complete system, including an emulation of a Turing complete system running in Life itself, for example Paul Chapman's emulation of a univeral Minsky Register Machine which is itself also finite. Combining these things means we can (in theory at least) construct a finite sized self-interpreter for Conway's Life that can interpret/emulate any other finite initial pattern in finite time. No doubt this self-interpreter would have a fairly high eigenratio though. :-)
On the other hand, a standard Turing Machine cannot emulate an infinite initial Life pattern in finite time -it'll never get past the first generation! However, the "Unit Cell" tiling can emulate any Life pattern, finite or infinite by virtue of its infinite parallelism.
As for high versus low eigenratios, I'm still interested in the low end. Dean Bell's Unit Cell pattern is not necessarily the most efficient implementation. In fact it is almost certainly not - although at the same time I have absolutely no idea how to improve it! As far as I can see there could be some very much smaller pattern that still achieves the same "effect" in some way or other. Another aspect of this that has been floating through my mind lately is the thought that Life's most efficient such "self-interpreter" (assume some "square pattern" that can be used to tile the whole universe) might be something that is very non-regular and difficult for the human eye/mind to easily discern or understand - for example whether the cell is alive or dead might not be something as simple as looking in one area of the pattern but some more complex feature/property.
Anyway, I'm definitely rambling now so I'll stop here!
Hi Clive,
This is Robyn. Bron linked me to your blog. Not being a programmer, I read your first two blogs, and couldn't help but think that I needed a self-interpreter to understand what you were talking about. I still found it fascinating enough to read right through to the end. You would't be INTP by any chance??
Cheers
Robyn
Post a Comment
<< Home