Life and Golly
Apr. 24th, 2011 09:32 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mmcirvinI've mentioned this before, a few years ago, but it's worth mentioning again: Golly is an extraordinarily good PC/Mac/Linux implementation of Conway's Game of Life, the most famous and extensively studied cellular automaton. The first time I found it, it was very new, but it's matured since then.
It can implement many other cellular automata as well; a notable thing that now ships with it is a fully functioning implementation of von Neumann's 1940s replicator, which used a more complex cellular automaton. There are lots of CAs with simple self-replicating patterns in them, but von Neumann wanted to show how one could function under more general conditions with a universal construction mechanism--which is pretty much the way living cells reproduce. Conway Life is sufficiently powerful that a replicator could function this way, but nobody's yet built one.
Update: In May 2010, Andrew Wade announced a universal-constructor-based spaceship called Gemini, that is, a replicator based on a universal constructor that destroys its parent, thereby translating itself to another place. This is a major development--it's apparently a lot smaller and faster than people had predicted a replicator could be. I'm not sure whether there are any obstacles to making a von Neumann-style replicator instead (presumably there would have to be some way of deactivating the parent instead of erasing it).
The most remarkable thing about Golly is its ability to use the hashlife algorithm. This is a Life engine that, for sufficiently regular patterns, can run them over spans of space and time so huge that a straightforward representation couldn't fit in a computer constructible in the observable universe. For simple cases, it's easy to see how this might be done: if I gave you, say, the first several cycles of a glider and then asked you to give me a precise description of the pixel array at time tick 10100, it probably wouldn't be that hard for you to do it, even though a square grid containing all the active pixels would have over 10198 pixels and that run is far longer than the life of the universe at one femtosecond per tick; because the behavior of the glider is regular and predictable. Hashlife builds on this idea.
Golly seems to have enabled a lot of interesting recent research into large Life patterns, many of which ship with the program (there are easy ways of importing others). Here's a news blog and a wiki of patterns and related information.
It can implement many other cellular automata as well; a notable thing that now ships with it is a fully functioning implementation of von Neumann's 1940s replicator, which used a more complex cellular automaton. There are lots of CAs with simple self-replicating patterns in them, but von Neumann wanted to show how one could function under more general conditions with a universal construction mechanism--which is pretty much the way living cells reproduce. Conway Life is sufficiently powerful that a replicator could function this way, but nobody's yet built one.
Update: In May 2010, Andrew Wade announced a universal-constructor-based spaceship called Gemini, that is, a replicator based on a universal constructor that destroys its parent, thereby translating itself to another place. This is a major development--it's apparently a lot smaller and faster than people had predicted a replicator could be. I'm not sure whether there are any obstacles to making a von Neumann-style replicator instead (presumably there would have to be some way of deactivating the parent instead of erasing it).
The most remarkable thing about Golly is its ability to use the hashlife algorithm. This is a Life engine that, for sufficiently regular patterns, can run them over spans of space and time so huge that a straightforward representation couldn't fit in a computer constructible in the observable universe. For simple cases, it's easy to see how this might be done: if I gave you, say, the first several cycles of a glider and then asked you to give me a precise description of the pixel array at time tick 10100, it probably wouldn't be that hard for you to do it, even though a square grid containing all the active pixels would have over 10198 pixels and that run is far longer than the life of the universe at one femtosecond per tick; because the behavior of the glider is regular and predictable. Hashlife builds on this idea.
Golly seems to have enabled a lot of interesting recent research into large Life patterns, many of which ship with the program (there are easy ways of importing others). Here's a news blog and a wiki of patterns and related information.