The X-rule: universal computation in a non-isotropic Life-like Cellular Automata.
Cite as:
Gómez Soto José Manuel and Wuensche Andrew: X-rule: universal computation in a non-isotropic Life-like Cellular Automata. Published in Journal of Cellular Automata.
Download paper from Arxiv: PDF
X-rule in DDlab: xrule.rul
X-rule in Golly: xrule.rule
Abstract
We present a new Life-like cellular automaton (CA) capable of logic universality: the X-rule. The CA is 2D, binary, with a Moore neighborhood similar to the game-of-Life, but is not based on birth/survival and is nonisotropic. We outline the search method. Several glider types and stable structures emerge spontaneously within X-rule dynamics. We construct glider-guns based on periodic oscillations between stable barriers, and interactions to create logical gates.
1) Searching for gliders
The first step was to search CA rules for emergent gliders and stable structure. In order to do that we fixed the parameter to be similar to the game-of-Life, and use the variability of inputentropy, see bellow figure . Like Sapin the search was restricted to isotropic rules only (equal outputs for any neighborhood rotation, reflection, or vertical flip) where rule-space is reduced to 2102. The result was a very large rule sample, from we take a shortlist of about 70 rules in the ordered sector of figure with both gliders and stable structures. Five rules, with gliders travelling both orthogonally and diagonally, were selected for further study.
2) Glider-gun's.
X-rule's glider-guns is building from a kit of parts, gliders and reflectors, that can be put together in many combinations to produce periodic oscillators based on bouncing/reflecting behaviour ? pairs of gliders bouncing against each other and trapped between reflectors from which other glider types are ejected at periodic intervals. The main idea to build a glider-gun was to build a periodic bouncing-colliding structure, a dynamical oscillator driving periodic collisions, which eventually, with some modication to the pattern or rule, might eject gliders. In this way, from the nal short-list of 5 isotropic rules, we selected a rule (X-rule precursor), where bouncing from collisions was observed. This bouncing behaviour was promising because it could provide components for a periodic bouncing-colliding structure. DDlab file: [gga.eed (180 x 180 space size)], Golly File:[gga.rle].
Glider gun 'c' shooting Gc gliders North, East, and an alternative towards the West, demonstrating that Gc glider-streams can be projected in any or- thogonal direction, though there may be different or simpler arrangements to achieve the same results. DDlab file: [CggcN.eed (180 x 180 space size)], Golly file: [CggcN.rle].
X-rule is Powered by DDlab and Golly
and
Download DDlab from: here
Download Golly from: here
3) Gliders of X-rule have a high probability to emerge from a random initial condition.
DDlab file: [random.eed (100 x 100 space size)], Golly file: [random.rle].
4) Compound glider.
The basic glider-guns are restricted to preferred directions because of non-isotropy. However, compound glider-guns for Gc and Ga allow any direction. These are constructed from two or more basic glider-guns and eaters/reflectors, positioned and synchronised precisely, making self-contained and sustainable multiple oscillating colliding compound structures. DDlab file: [ggaNEsok.eed (200 x 200 space size)], Golly File: [ggaNEsok.rle].
5) Logic universality.
To demonstrate the X-rule's logic universality we followed the game-of-Life method using glider-guns as pulse generators, to construct logical gates NOT, AND, OR, and finally the functionally complete NAND gate a combination of NAND gates can implement any logic circuit. In a glider-stream, the presence of a glider represents 1, and a gap 0. When two suitably synchronised glider-streams intersect, gliders either collide and self-destruct leaving a gap, or a glider passes through a gap and survives. Logical gates are implemented by combining perfectly spaced and synchronised input streams with intersecting glider-streams generated by one or more glider-guns. All the gates in various orientations have been demonstrated[6]. As an example we show a NAND gate with the output directed NW. DDlab file: [sayabor.eed (200 x 200 space size)], Golly file: [sayabor.rle].
Video about Game of Life.
