OCA:Logic Rule
| Logic Rule | |
| Rulestring | /2ae B2ae/S |
|---|---|
| Character | Miscellaneous |
Logic Rule (or LogicRule) is a minimalistic isotropic non-totalistic cellular automaton devised by David Conant in March 2001. It is one of the early demonstrations showing how signal circuitry can be built in simple cellular automata.
In this rule, a cell is alive the next generation if it is currently dead and exactly two neighbouring cells are alive, and those two cells are connected to each other either orthogonally or diagonally. With Hensel notation[note 1] this is expressed as B2ae/S. The rule was included as a built-in "general binary" rule in Mirek's Cellebration along with several patterns, but the program uses another notation which turned out to be inaccurate later.[1]
Signal logic
The transition B2a indicates that a domino is a linear replicator at c orthogonal following Wolfram's Rule 90, whereas B2e allows for the existence of a family of Margolus oscillators (see the following section), the smallest of which is the period-2 duoplet (originally named "#2 Oscillator"). Meanwhile, there are two small photons (lightspeed gliders): the first of which is the period-1 moon as in seeds, and the second is the period-2 banana. Serving as the basic unit of information in signal circuitry, any of them may also be called a "bit" and the presence/absence in a "bit stream" can be encoded in binary as 1/0.
Bit stream generators
Guns for both of the photons can easily be constructed from dominoes and duoplets, as an interaction between two dominoes gives two moons as well as two shifted dominoes; and duoplets can suppress dominoes from replicating, eat a moon, or convert a moon to a banana. The smallest known moon gun operates at period 8, and is called an "Index Bit Stream Generator" (IBSG).
| IBSG and a p8 banana gun based on it (click above to open LifeViewer) |
IBSG is systematically called #9 BSG, where the index #9 indicates a distance of 9 cells between the domino and the duoplet. A number of BSGs with larger indices of the form 8n + 1 are documented by comparing their output streams with the IBSG. For example, the next smallest member is #17 BSG that emits a string of 110's with period 3. The actual period measured in ticks is 3 × 8 = 24.
| The #17 BSG (click above to open LifeViewer) |
It appears that the period of n-th BSG follows Sloane's 
A086839 and log₂(period + 1) almost follows Sloane's A003558 except for the #145 BSG in the following list. Here the contents of bit outputs are calculated with a C program.
Click on "Expand" to the right to view statistics and bit outputs for selected BSGs. Only the first eight and last eight bits are shown for long strings; click on them to toggle the view of full strings.
| Index | Statistics | Content | ||
|---|---|---|---|---|
| Period | log₂(Period+1) | Brief | Full | |
| 9 | 1 | 1 | 1 | |
| 17 | 3 | 2 | 110 | |
| 25 | 7 | 3 | 1101001 | |
| 33 | 7 | 3 | 1101000 | |
| 41 | 31 | 5 | 11010001...00110111 | 1101000100101011
000011100110111 |
| 49 | 63 | 6 | 11010001...01111110 | 1101000100001011
0010101001001111 0000011011100110 001110101111110 |
| 57 | 15 | 4 | 110100010000001 | |
| 65 | 15 | 4 | 110100010000000 | |
| 73 | 511 | 9 | 11010001...01111111 | 1101000100000001
0010101000001011 0000010001001110 0010101011101101 0000001010110010 0001000011110100 1010011001001100 0111111011111011 0000101000101110 0100010100101110 1010001100101000 0101111100010010 0100011010110110 1011100011011000 1011011101110100 1101010101001111 0000000011100110 0000011011111100 0011101000011001 1010010011111110 0110111000001111 1010110001100010 0011101111010101 1010100100000110 0001101000111100 1110010110011110 1110011111001010 1111000111000010 0110110110010111 1011011110010010 1101001110110011 001110101111111 |
| 81 | 63 | 6 | 11010001...00110110 | 1101000100000001
0000101000101011 0000000001101110 000011100110110 |
| 89 | 2047 | 11 | 11010001...01101001 | 1101000100000001
0000001010100011 0000000010100110 0100011010100111 0000101000101010 0100010000111110 0001000010110110 0110110010010111 0000000001001110 0010111001001110 1011001000010010 0010111101110110 0000101100101000 1110011100111110 1011011011110000 1100101110011101 0010101000001010 0001000001011110 0000010001111110 1011100001110110 0100010100000110 1010100110001100 1010010011011111 1011110110010110 0000001011101101 0010111011101000 1111010010110101 0010010101011100 0100111100010110 1111011110001000 1101101001100111 1100101111010011 0000010001000100 1010001001001100 0010101100001000 1011001101011110 1010001000111000 0001111101111100 0110111101000010 1001011110011100 0001001010110011 0010101010010110 0100110011000011 0110000001011010 1110011010011010 0101001101010111 0110011111110001 1100100100111110 0010101010101100 0101011011111001 0000111001010100 1111110001001000 0101010110110000 1100010100011011 1010010010010001 1001001111011000 1011000011111111 0000000110011110 1111111110011101 1100001001100010 1111100111100110 0011110000010101 1111000001101101 1101101110001101 0000000000111010 0001101000111010 0110111000001110 0001101011010010 0000011011100111 1010001011101010 0110110110101111 1011100101110100 1110011000000110 0000111111001010 0000001111010101 1001011111010010 0011110011111101 1001100010000100 0110001110110101 0110101101110010 0000000110100100 1110010110100111 1010110001101100 1110001100110100 0011101011110010 0101001010000111 1011011000100010 1011100101001110 1111110000111100 0110000111000100 0001100100000111 1001000100110101 1001111000010111 1111010100101011 1101101011000001 1000110101110100 0000111001101110 1110011001110010 0011101110111110 1101111111001001 1010001001110110 0011000100110010 1101110101010000 1011100011101010 0001100110011011 1100110110101000 1111101000110011 1010101111000111 1100110010010000 0100001100001001 0110001110001111 0111000101001000 0110111110101010 1111111101110101 1010101010001011 0100000111011110 0101011101011101 1110101111110011 0101000000100100 1011011010000100 1111111111101001 1111011000010110 0010010111111010 0000100110110001 1111110110100010 1001111001011001 1101101101100101 011010001101001 |
| 97 | 1023 | 10 | 11010001...11101000 | 1101000100000001
0000000010100011 0000001010100010 0100010010100111 0000000000101110 0100111000101110 0001001010110010 0100111010010111 0010101000001010 0000010001011110 0001000001010110 1010110001110110 0000000100101110 1110110100101100 1011000011110110 1110100110010111 0000010001000100 0010101001001100 1010001000011000 0011101101011100 0000101100101010 1011001100111100 1110011001011010 1001111110010110 0010101010101001 0000011011111100 0101010011110001 1010110001011000 0100111100000000 1111111110011110 1111111001100001 1100001110011101 0000000000011010 0011101000011010 0000111001101110 0011101001110010 1110011000000110 0000001111001010 0000111111001101 1001101111010010 0000000011100101 1010010011100100 0110111110101101 1010011101110010 1111110000111100 0001100111000100 0110000111110111 1110100100110100 0000011011100110 0110111011101011 1010001000110110 0111010101110010 0001100110011000 1111110110101011 1100110001010000 1001101111001000 0011101011111111 1010101010001010 0101010111011111 0100000101110100 1111111111110110 0001011000001001 1111101000100101 111010011101000 |
| 105 | 511 | 9 | 11010001...10110111 | 1101000100000001
0000000000101011 0000101000101010 0000010001101111 0000000001000100 1010011001000110 0000101000111000 1011011001111101 0000001010100010 0001000010110010 0100010000010110 1011001010111110 0010101001001110 1010011101001000 0100111100111100 1001110111011011 0000000000001110 0110111000001110 0000000110100010 0110110110101100 0011101000011010 0000001110111110 1110011110100100 0110110101010110 0000011011100110 0001101011011100 1110011000111111 1011100011000010 0011101001110101 1010111111010010 1110100111110011 110110110110111 |
| 113 | 16383 | 14 | (See archieve) | |
| 121 | 31 | 5 | ||
| 129 | 31 | 5 | ||
| 137 | 4095 | 12 | ||
| 145 | 87381 | 16.3244 | (See archieve) | |
| 153 | 4095 | 12 | ||
| 161 | 1023 | 10 | ||
| 169 | 127 | 7 | ||
| 177 | 4095 | 12 | ||
| 185 | 8388607 | 23 | ||
| 193 | 2097151 | 21 | ||
| 201 | 255 | 8 | ||
| 209 | 67108863 | 26 | ||
| 217 | 1048575 | 20 | ||
| 225 | 511 | 9 | ||
From another point of view, any BSG with width 8 n + 1 generates the output of a linear-feedback shift register[note 2] (LFSR). Only numbers from Sloane's A123399 generate maximum length LFSRs with periods of 2n - 1.
The highest number listed is 419 which has a period of 2419 - 1, about 1.35 × 10126 before the output repeats.
| A123399 |
Width | Period |
|---|---|---|
| 1 | 9 | 1 |
| 2 | 17 | 3 |
| 3 | 25 | 7 |
| 5 | 41 | 31 |
| 6 | 49 | 63 |
| 9 | 73 | 511 |
| 11 | 89 | 2,047 |
| 14 | 113 | 16,383 |
| 23 | 185 | 8,388,607 |
| 26 | 209 | 67,108,863 |
| 29 | 233 | 536,870,911 |
| 30 | 241 | 1,073,741,824 |
| 33 | 265 | 8,589,934,592 |
| 35 | 281 | 34,359,738,368 |
| 39 | 313 | 549,755,813,887 |
| 41 | 329 | 2,199,023,255,551 |
| 51 | 409 | 2,251,799,813,685,247 |
| 53 | 425 | 9,007,199,254,740,991 |
When removing the two terminal duoplets of a BSG, the dominoes replicate unboundedly and result in a non-repeating bit stream generator (XBSG). Its output string is predictable, though; the 1's appear at 1, 2, 4, 8, ..., 2n-th place and the rest is sea of 0's. This is listed in Sloane's A036987, the Fredholm-Rueppel sequence. An equivalent device akin to a caber tosser can be designed with only one unbounded replicator and two IBSG's, so that signals from the other stationary end can be fed into circuitry easily; the n-th output starting from 0 arrives at the shown location at generation 2n + 3 - 8.
| XBSG, or Fredholm-Rueppel sequence generator (click above to open LifeViewer) |
| The equivalent device with only one side of the bounding box growing infinitely (click above to open LifeViewer) |
Logic gates
Photon interactions can be used to demonstrate logic gates, and arranging input(s) and IBSG(s) suffices to construct any of the gates. The simplest case, a NOT gate forms by colliding an intermittent p8 input stream with an IBSG coming orthogonally at certain timing. For each of the 1's in the input stream, a 2-banana annihilation occurs, while each of the 0's allows for a banana to pass through the intersection, thus effectively carrying out inversion.
| The BSGs used as signal sources are: A = BSG2 width 17, B = BSG3 width 25 (click above to open LifeViewer) |
| NOT A (click above to open LifeViewer) |
| A AND B (click above to open LifeViewer) |
| A NAND B (click above to open LifeViewer) |
| A OR B (click above to open LifeViewer) |
| A NOR B (click above to open LifeViewer) |
| A XOR B (click above to open LifeViewer) |
Other patterns
Despite its name, there are more "naturalistic" patterns of note beyond logic circuitry in Logic Rule. Consider a class of extended photons similar to the moon, with one "wing" fixed and the other of variable length. The first two cases are the banana (with length 0) and the moon (with length 1). At length 2 as shown to the right, the pattern is a predecessor of a period-2 spaceship. Depending on the length, these extended photons have different fates and may become either a spaceship or a puffer. The first few cases are tabulated below, with links to the corresponding objects on Catagolue at their first occurrence.
Click on "Expand" to the right to view the fates of this class of patterns.
| Length | Fate |
|---|---|
| 0 | A p2 spaceship (banana) |
| 1 | A p1 spaceship (moon) |
| 2 | A p2 spaceship |
| 3 | A p2 spaceship |
| 4 | A p4 spaceship |
| 5 | A p4 spaceship |
| 6 | A p4 puffer, 1 xp2_12 (duoplet, width 1) per period |
| 7 | A p4 spaceship |
| 8 | A p8 spaceship |
| 9 | A p8 spaceship |
| 10 | A p8 puffer, 2 xp2_12 per period |
| 11 | A p8 spaceship |
| 12 | A p8 puffer, 1 xp6_1248 (width 1) per period |
| 13 | A p8 puffer, 1 xp4_25ak8 (width 2) per period |
| 14 | A p8 puffer, 1 xp14_0g8421z1 (width 1) per period |
| 15 | A p8 spaceship |
| 16 | A p16 spaceship |
| 17 | A p16 spaceship |
| 18 | A p16 puffer, 5 xp2_12 and 1 xp6_1248 per period |
| 19 | A p16 spaceship |
| 20 | A p16 puffer, 3 xp6_1248 per period |
| 21 | A p16 puffer, 2 xp4_25ak8 per period |
| 22 | A p16 puffer, 2 xp14_0g8421z1 per period |
| 23 | A p16 spaceship |
| 24 | A p16 puffer, 1 xp14_xg8421z421 (width 1) per period |
| 25 | A p16 puffer, 1 xp12_xg8ka52z4a521 (width 2) per period |
| 26 | A p16 puffer, 1 xp62_1248gzy11248g (width 1) per period |
| 27 | A p16 puffer, 1 xp8_xg8kalak8z4alala521zx1 (width 4) per period |
| 28 | A p16 puffer, 1 xp126_y3g8421zwg8421z21 (width 1) per period |
| 29 | A p16 puffer, 1 xp28_y3g8ka52zwg8ka521z2521 (width 2) per period |
| 30 | A p16 puffer, 1 xp30_1248gzy11248gzy61248 (width 1) per period |
| 31 | A p16 spaceship |
| 32 | A p32 spaceship |
| 33 | A p32 spaceship |
| 34 | A p32 puffer, 14 xp2_12, 4 xp6_1248 and 1 xp4_25ak8 per period |
| 35 | A p32 spaceship |
| 36 | A p32 puffer, 5 xp2_12, 4 xp6_1248, 1 xp4_25ak8 and 1 xp12_xg8ka52z4a521 per period |
| 37 | A p32 puffer, 5 xp4_25ak8 and 1 xp12_xg8ka52z4a521 per period |
| 38 | A p32 puffer, 4 xp2_12, 4 xp14_0g8421z1 and 1 xp14_xg8421z421 per period |
| 39 | A p32 spaceship |
| 40 | A p32 puffer, 3 xp14_xg8421z421 and 1 xp2_12 per period |
| 41 | A p32 puffer, 3 xp12_xg8ka52z4a521 per period |
| 42 | A p32 puffer, 2 xp2_12, 2 xp6_1248, 2 xp62_1248gzy11248g and 1 xp4_25ak8 per period |
| 43 | A p32 puffer, 2 xp8_xg8kalak8z4alala521zx1 per period |
| 44 | A p32 puffer, 2 xp126_y3g8421zwg8421z21 and 1 xp14_0g8kala4z12521 per period |
| 45 | A p32 puffer, 2 xp28_y3g8ka52zwg8ka521z2521 per period |
| 46 | A p32 puffer, 2 xp30_1248gzy11248gzy61248 per period |
| 47 | A p32 spaceship |
| 48 | A p32 puffer, 1 xp30_y7g8421zy2g8421z0g8421z1 (width 1) per period |
| 49 | A p32 puffer, 1 xp28_y7g8ka52zy2g8ka521z0g8ka521z121 (width 2) per period |
| 50 | A p32 puffer, 1 xp1022_y9g8421zy4g8421zxg8421z421 (width 1) per period |
| 51 | A p32 puffer, 1 xp24_8kalak8gzw125alalak8gzy3125alalak8gzy8125a521 (width 4) per period |
| 52 | A p32 puffer, 1 xp126_1248gzy11248gzy61248gzyb1248g (width 1) per period |
| 53 | A p32 puffer, 1 xp124_ybg8ka52zy6g8ka521zy1g8ka521zg8ka521z01 (width 2) per period |
| 54 | A p32 puffer, 1 xp4094_ydg8421zy8g8421zy3g8421zwg8421z21 (width 1) per period |
| 55 | A p32 puffer, 1 xp16_wg842101248gzahy71248gzw1248gy71248gzy31248gy3g842zy81240421 (width 8) per period |
| 56 | A p32 puffer, 1 xp2046_1248gzy11248gzy61248gzyb1248gzyg1248 (width 1) per period |
| 57 | A p32 puffer, 1 xp252_25ak8gzy0125ak8gzy5125ak8gzya125ak8gzyf125ak8 (width 2) per period |
| 58 | A p32 puffer, 1 xp1022_yhg8421zycg8421zy7g8421zy2g8421z0g8421z1 (width 1) per period |
| 59 | A p32 puffer, 1 xp56_8kalak8gzw125alalak8gzy3125alalak8gzy8125alalak8gzyd125alalak8zyi121 (width 4) per period |
| 60 | A p32 puffer, 1 xp32766_yjg8421zyeg8421zy9g8421zy4g8421zxg8421z421 (width 1) per period |
| 61 | A p32 puffer, 1 xp60_yjg8ka52zyeg8ka521zy9g8ka521zy4g8ka521zxg8ka521z4a521 (width 2) per period |
| 62 | A p32 puffer, 1 xp62_1248gzy11248gzy61248gzyb1248gzyg1248gzyl1248g (width 1) per period |
| 63 | A p32 spaceship |
| 64 | A p64 spaceship |
| 65 | A p64 spaceship |
| 66 | A p64 puffer, 41 xp2_12, 8 xp6_1248, 6 xp4_25ak8, 1 xp12_xg8ka52z4a521 per period |
| 67 | A p64 spaceship |
Several trends can be found from the list for positive lengths.
- Regardless of the type, a length-n extended photon has a period of 2floor(log₂(n)), i.e. Sloane's
A053644(n). - A length-n extended photon will converge to a spaceship if n is in Sloane's A099627. A vanishing T-square fractal[note 3] can be seen at the tail for large enough n close to some power of 2.
- A length-n extended photon will converge to a clean puffer leaving one oscillator per period if n not in A099627 and 3 × 2k ≤ n ≤ 2k + 2 for some positive integer k. Its trailing end is divided into two halves, one becomes a disappearing spark from a diagonal line of 2k + 1 - 1 cells while another evolves into the oscillator.
- The oscillators are square and oscillate according to a block cellular automaton on the Margolus neighbourhood. Previously the phenomenon was observed and studied in an outer-totalistic rule called 2×2, where the oscillators are made up of 2 × 2 blocks, followed by several other non-totalistic rules later.[2][3] Here the oscillators can be seen as composed of tubs, though it is not the smallest element because width-1 forms as labelled above exist. A width-1 diagonal line of 2m cells has a period of Sloane's A160657(m), and appears in the list above at length n = A079946(m), or Sloane's A049039(m)-th place among oscillators. Other diagonal widths are resulted from inflation by a factor of 2k × 2k, which also multiplies the period by 2k.
- The oscillators are square and oscillate according to a block cellular automaton on the Margolus neighbourhood. Previously the phenomenon was observed and studied in an outer-totalistic rule called 2×2, where the oscillators are made up of 2 × 2 blocks, followed by several other non-totalistic rules later.[2][3] Here the oscillators can be seen as composed of tubs, though it is not the smallest element because width-1 forms as labelled above exist. A width-1 diagonal line of 2m cells has a period of Sloane's
- An extended photon is dirty if its length does not satisfy any requirements above. In particular, a period-2k extended photon produces the largest amount of ash if its length is 2k + 2. Behind a puffer of this kind, straight diagonal lines replicate and decay in a complex manner leading to configurations with some self-similarity.
- However, no matter how dirty the ash is, it is guaranteed not to emit photons or replicators because B2e-governed evolution will only have new cells born at the same checkerboard parity, therefore prohibiting domino frontend from forming.
- Regardless of the type, the reaction envelope of the tail is limited to one side of the extended photon. This implies that it can have two halves extended independently; not only their length can be different, but also they can operate at different periods with any phase difference.
Apart from the long extended photons above, the emergence of patterns may also be observed with smaller seeds, for instance the diagonally symmetric tetraplet shown to the right. If random soups are put behind the long diagonal line after a while to perturb the wavestretcher, the outcome will be more complicated.[4]
Notes
- ↑ Hensel notation is a rulestring notation for isotropic rules, supported in CA simulation software including Golly and LifeViewer.
- ↑ Linear-feedback shift register at Wikipedia
- ↑ T-square fractal at Wikipedia
References
- ↑ Jeremy Tan (November 30, 2018). Interpreting MCell's "general binary" rule family (discussion thread) at the ConwayLife.com forums
- ↑ Dave Greene (December 25, 2017). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
- ↑ Dave Greene (December 26, 2017). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
- ↑ blah (January 10, 2017). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
External links
- Cellular Automata Logic Rule at logic-ca.com (Jan 2005 archive on the Wayback Machine; currently down) - note: the author claims to have all of the files for this web site, but it's not currently hosted anywhere. NOTE: The files for the original website are now permanently stored on a Google shared folder.
- Google Shared Folder where all of the files for the original Logic Rule web page are stored.
- LogicRule at Adam P. Goucher's Catagolue
- MCell built-in General binary rules: LogicRule at Mirek Wójtowicz's Cellebration page
- BSG info Google spreadsheet
- LIFE050.COM Zip file with the DOS program where the author originally discovered the Logic Rule. You will need DOSBox or another DOS emulator to run it.
- BSG.c Original C program used to generate output and period.