1. Introduction
John Horton Conway’s Game of Life is a simple two-dimensional, two state cellular automaton (CA), remarkable for its complex behaviour. That behaviour is known to be very sensitive to a change in the CA rules. Here we continue our investigations into its sensitivity to changes in the lattice, by the use of an aperiodic Penrose tiling lattice.
Section 2 describes Penrose tilings; section 3 generalises the concepts of neighbourhood and outer totalistic CA rules (which include the Game of Life) to aperiodic lattices, and introduces a naming convention for Penrose Life oscillators. Section 4 presents various Penrose lattice still life configurations; sections 5–8 present various oscillators with periods from 2 to 15. Section 9 presents an algorithm to detect oscillators, and a means to classify them based on their underlying neighbourhood graph.
10. Summary and Conclusions
We have continued our investigations of the Game of Life on Penrose tilings, producing a preliminary catalogue of still lifes and oscillators, including comparisons with similar oscillators on the regular Life tiling. We have catalogued many still life and periodic oscillators, on both kite and dart and rhomb tilings. We have also demonstrated that arbitrarily large snakes and chains can exist. We have found no propagating features analogous to gliders, but the existence of “fuses” burning along chains makes us optimistic that such structures may be discovered.
We have introduced an identification code to help refer to different oscillators. However, it does not completely distinguish different oscillators (although collisions are rare, except among the still lifes). There are visually variant forms due to changes in the tiling (for example, the variant oscillators on different SC extensions); these have the same code. But a few oscillators that are obviously of a different form also share the same code. We further distinguish these by considering the underlying oscillator graph, which captures the topology of oscillator cells neighbourhoods.
The oscillator graph by itself is also insufficient to completely distinguish different oscillators (although collisions are again rare). The combination of code and oscillator graph has, so far, proved sufficient to unify isomorphic forms whilst discriminating different oscillators.
Isomorphic forms can exist on one, two, or all three tilings. For example, several variants of the bats and of dancers exist on the kite and dart tiling; marchers, breathers, and ninjas exist on both kite and dart and rhomb tilings; tubs, blocks, snakes, and blinkers exist on all three tilings. If an oscillator exists on both the regular and one of the Penrose tilings, then it tends to exist on the other Penrose tiling, too. The only exception in this catalogue is that we have not been able to find a kd-p1-8 snake, despite there being a regular Life form (the very long snake) and a rhomb form.
Our classification of disconnected oscillators requires the inclusion of gamma-cells: cells that are always dead, but whose removal would destroy the oscillator.We define a further macroscopic oscillator graph, to provide a form of isomorphism between disconnected oscillators with different numbers of gamma-cells.
Further work includes extending the catalogue. Regular Life has very many small oscillators; we suspect that our preliminary catalogue of Penrose oscillators has identified only a small proportion of them; a more systematic search is needed. Additionally, larger and longer period oscillators are still to be found. Here an evolutionary search might be more appropriate.
Oscillators themselves, although demonstrating that Penrose life is complex, are not the ultimate goal. That would be to use Penrose life to implement larger computations in a way analogous to regular Life. We have made a start by suggesting that “fuses” can be used to propagate information, or to implement timers. Many more such components are needed: a starting place is to look at the structures and interactions of small oscillators.
