|The largest collection of online information about Conway's Game of Life and Life-like cellular automata. Contains over 900 articles.|
|Share discoveries, discuss patterns, and ask questions about cellular automata with fellow enthusiasts.|
|Golly is a free program that allows you to easily explore much larger patterns at higher speeds than any web-based applet ever could.|
Now that the Conway's Life replicator pattern is in working order, what might the next step be?
The phase-shifted linear replicator isn't really a very satisfactory design. Each parent pattern can produce only one child pattern, which then blocks it from any further replication. It seems as if a quadratic-growth, space-filling replicator would be much more in keeping with von Neumann's (and Conway's) original purpose.
One major limitation of essentially linear designs like the Gemini spaceship and Geminoid replicator is that replication and movement perpendicular to the long stream of gliders is fairly easy, but it's very hard to make a new copy in the other direction -- just because it means constructing the far end of the new copy millions of cells away.
This is intended to be a follow-up to my earlier post on cp4space (mentioning Mike Playle's new reflector). The content of this post is slightly too niche for cp4space, so I've included it here instead.
Mike Playle's new reflector has prompted a new surge in activity, with several derivative patterns being constructed. Firstly, Dave Greene has utilised the 'Snark' to reduce the area of the period-59 gun (Goucher and Summers) by two orders of magnitude.
Secondly, a contributor on Nathaniel Johnston's forum has found a way to synthesise the reflector using 50 gliders. There has been much interest about the constructibility and destructibility of reflectors, with Paul Chapman writing a program entitled Seeds of Destruction to search for efficient self-destruction circuits. This is part of an ongoing project by Chapman and Greene to produce a smaller replicator than Andrew Wade's Gemini. A preliminary edition of Seeds of Destruction can be downloaded from here.
Josh Ball has discovered a microscopic orthogonal spaceship with a new velocity, namely c/7. It is the slowest orthogonal spaceship, which (together with its loaf-pushing behaviour) led to it being named 'the loafer'. Adam P. Goucher discovered how to synthesise it with 18 gliders; this was further reduced to 8 by Matthias Merzenich. Shortly afterwards, a gun was engineered to repeatedly emit the spaceship.
A summary of the known orthogonal spaceship speeds is given in the following diagram, using Ford circles to represent rational numbers:
HighLife differs quantatively from Conway's Game of Life due to an additional birth condition: if a dead cell is surrounded by six live neighbours, it becomes alive. Qualitatively, the main difference between Life and HighLife is that the replicators in Life are imagined to be very large (no explicit examples have been discovered, although the technology behind Gemini could be adapted to yield one), whereas there is a nice small example in HighLife.
Soon after the discovery of the replicator, it was realised that it could be tamed into a c/6 spaceship by pulling a blinker behind it. In 1999, Dean Hickerson proposed the existence of spaceships with much slower velocities, obtained by pushing junk at one end of a replicator track and pulling it at the other end. No explicit examples of spaceships were discovered this way, although Dean found a workable push reaction. This was mentioned on David Eppstein's website and in a chapter he wrote for Game of Life Cellular Automata.
It was pretty much forgotten for 14 years, until Adam P. Goucher wrote a search program to attempt to construct replicator tracks capable of forming spaceships. Initially, he found a c/69 spaceship with over 84 billion replicator units; his results and method of searching are summarised on Complex Projective 4-Space. Due to its immense size, slow movement and general appearance, it was named the Basilisk. Karel Suhajda commented on the post, suggesting trying different speeds. Tweaking the search parameters resulted in a c/63 spaceship with about 2 billion units; however, this was still prohibitively large for Golly.
Self-replication in Conway's Life has been a topic for discussion and research from the very beginning, over forty years ago now (!). The original purpose of Conway's Life was to find a simplification of John von Neumann's self-replicating machine designs, which used a CA rule with 29 states. A couple of non-constructive universality proofs for B3/S23 Life were completed very early on, though they were never published in detail -- and my sense is that actual self-replicating patterns along the lines of these proofs would require something on the order of a planet-sized computer and a geological epoch or two to simulate a replication cycle.
The technology to build a Conway's Life replicator out of stable parts has been available since at least 2004. A working pattern could certainly have been put together in a few years by a full-time Herschel plumber, with a high-energy glider physicist or two as consultants. But unfortunately there seem to be very few multi-year grants available for large-scale CA pattern-building -- even for such obviously worthwhile Holy-Grail quests as this one!
In 2009, Adam P. Goucher put together a working universal computer-constructor that could be programmed to make a complete copy of itself. The pattern, however, is so huge and slow that it would have taken an enormous amount of work to program it to self-replicate -- it would have been easier to come up with a new replicator design from scratch. Clearly, in hindsight, everyone was waiting for something better to come along.
A wealth of new generalised Herschel conduits have been discovered recently, even since the latest update on LifeNews. A member of the ConwayLife.com forums with the alias 'Guam' has successfully built a stable 90-degree reflector with a repeat time of 444 generations, marginally faster than its 466-tick predecessor.
The core of the reflector is a staged-recovery mechanism found in an earlier 487-tick reflector. The speed-up is therefore achieved by surrounding the core with a more efficient Herschel track (exploiting the new conduits), enabling the gliders to be delivered to the active site faster than before.
In other news, there is now a continuous version of the Game of Life exhibiting rich behaviour. It cannot be simulated in Golly due to its incompatibility with HashLife, although I believe the next release of Ready will incorporate it.
As detailed over on Complex Projective 4-Space, I computed some large images of the Mandelbrot set. For example, here is part of a screenshot of Golly, looking at the Seahorse Valley in the Mandelbrot set:
With Golly, we can run the Mandelbrot set in a cellular automaton. The results are fairly uninteresting with B3/S23, so I simulated the boundary (obtained from the original image by one generation of B3/S23) in HighLife (B36/S23) instead. As with all sufficiently large chaotic HighLife universes, profusions of replicators emerge:
You can download the files from Complex Projective 4-Space yourself if you're interested in running a simulation. For these purposes, you'll want the 262144 by 262144 monochromatic image (25 MB download as .mc.gz), rather than the scaled-down colourful version.
My apologies for the lack of recent postings. There are rumours that the LifeNews server may be turning off in the immediate future, so I was tentative about uploading something new. Nevertheless, Andrew Trevorrow convinced me that this deserves to be published on ConwayLife.com, and I understand this to currently be the most direct way of doing so.
The developers of Golly have recently turned their attentions to creating a new piece of software capable of supporting reaction-diffusion systems and cellular automata on arbitrary meshes. This has been discussed on Complex Projective 4-Space and The Aperiodical, amongst other places.
There has also been some work on cellular automata on Penrose tilings. Nick Owens and Susan Stepney investigated B3/S23 a while ago, writing a chapter about the topic in Adamatzky's Game of Life Cellular Automata. This summer, a couple of related, independent and almost simultaneous discoveries were made. One of these was a weakly universal cellular automaton on a Penrose tiling; the other was a glider.
Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels systematically searched the entire space of 10-by-10 patterns with fourfold rotational symmetry, finding a Garden of Eden with 92 specified cells (56 live, 36 dead). Moreover, they proved the non-existence of Gardens of Eden within a 6-by-6 box.