X-rule's Precursor is also Logically Universal.
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: prule.rul
X-rule in Golly: prule.rule
Abstract
We re-examine the isotropic Precursor-Rule (of the anisotropic X-Rule[6]) and show that it is also logically universal. The Precursor-Rule was selected from a sample of biased cellular automata rules classified by input- entropy. These biases followed most 'Life-Like' constraints (in par-ticular isotropy), but not simple birth/survival logic. The Precursor-Rule was chosen for its spontaneously emergent mobile and stable patterns, gliders and eaters/reflectors, but glider-guns, originally absent, have recently been discovered, as well as other complex structures from the Game- of-Life lexicon. We demonstrate these newly discovered structures, and build the logical gates required for universality in the logical sense.
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.
Although a diversity of interactions between gliders and eaters provides the first hint of potential universality, the essential ingredient is a glider-gun, a dynamic structure that ejects gliders periodically into space. A glider-gun can also be seen as an oscillator that adds to its form periodically to shed gliders. In some rules a glider-gun may emerge spontaneously but not in the Game-of-Life, the X-Rule, or the Precursor-Rule in these cases the glider-gun is a complex structure with a negligible probability of emerging from a random pattern it has to be found, discovered or somehow constructed. DDlab file: [ggas.eed (100 x 100 space size)], Golly File:[ggas.rle].
The 'QuadGG2a' shoots G2a, double Ga gliders and is significant because it provides the building blocks for meta-glider- guns made from interacting simpler glider-guns, including the Ga glider-gun discovered in 'conwaylife Forum'. DDlab file: [ggaw.eed (100 x 100 space size)], Golly file: [ggaw.rle].
Sayab-rule is Powered by DDlab and Golly
and
Download DDlab from: here
Download Golly from: here
3) Gliders of Precursor-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)Breeder.
TA breeder from 8 GGc glider-guns built by 'conwaylife forum'. Along the top, 6 GGc?s are aligned horizontally, one slightly above the next, from left to right, sending 6 Gc glider-streams South. The two remaining GGc?s are positioned above each other on the right and eject Gc gliders West. The upper Westward glider-stream is deflected downward (by the 6 top GGc?s) and the two Westward glider-streams finally merge into a complex combined glider-stream, creating a sort of rake that continues to sends Gc glider-streams South (at 90 grade) all along its length, starting at the tip. An eater below the merging zone is an essential component. DDlab file: [breeder.eed (300 x 300 space size)], Golly File: [breeder.rle].
5) Logic Universality.
An example of the OR gate: input string A (11001) and B (10101) both moving SE interact with a GGa glider-stream moving NE, and subsequently with GGa glider-stream moving SE, resulting in A-OR-B (11101) moving SE after 302 time-steps. Any two Ga input strings can be substituted for A and B. The dynamics making this OR gate first makes an intermediate NOT-A string 00110 (as in figure 19), which then interacts with string B to simultaniously produce both the AND and the NOR string as in figure 20. The intermediate A-NOR-B string 00010 is inverted by the upper glider-gun stream to make NOT(A-NOR-B) which is the same as A-OR-B. DDlab file: [or.eed (300 x 300 space size)], Golly file: [or.rle].
Video about Game of Life.
