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
