OCA:Logic Rule: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
No edit summary
Line 114: Line 114:


Thanks to B2e, the [[Margolus]] oscillators as in the [[OCA:Banks-I#Related rules|black-white reversal of Banks-I]] exist.
Thanks to B2e, the [[Margolus]] oscillators as in the [[OCA:Banks-I#Related rules|black-white reversal of Banks-I]] exist.
===Linear feedback shift registers===
Any BSG, with width is 8<i>n</i>+1 generates the output of a Linear Feedback Shift Register. Only numbers from {{OEIS|A123399}} generate maximum length LFSRs, and have periods of 2<sup><i>n</i></sup>-1.<br>
The highest number listed is 419 which has a period of 2<sup><i>419</i></sup>-1, about 1.35 x 10<sup><i>126</i></sup> before the output repeats.<br>
{| class="wikitable" style="margin-left:auto;margin-right:auto"
|-
! | {{OEIS|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,240
|-
| 53 || 425 || 9,007,199,254,740,990
|}


==References==
==References==

Revision as of 23:57, 17 August 2021

This article is a stub. You can help LifeWiki by expanding it.
Logic Rule
x=64, y = 64, rule = B2ae/S ! #C [[ THEME Inverse ]] #C [[ RANDOMIZE2 THUMBLAUNCH THUMBNAIL THUMBSIZE 2 GRID ZOOM 6 WIDTH 600 HEIGHT 600 LABEL 90 -20 2 "#G" AUTOSTART PAUSE 2 GPS 8 LOOP 256 ]]
LifeViewer-generated pseudorandom soup
Rulestring /2ae
B2ae/S
Character Miscellaneous

Logic Rule (or LogicRule) is a minimalistic isotropic non-totalistic Life-like 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 exactly two neighbouring cells are alive, and those two cells are connected to each other either orthogonally or diagonally. With Hensel notation this is expressed as B2ae/S. The rule is 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]

Patterns

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 oscillators, 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).

x = 66, y = 12, rule = B2ae/S 12b2o38b2o$11bo2bo39bo2$50bo$49bo2$bo8bo4bo8bo16bo8bo4bo8bo$o9bo4bo9bo 14bo9bo4bo9bo3$13bo39bo$12bo39bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ ZOOM 8 ]]
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.

x = 42, y = 6, rule = B2ae/S bo16bo4bo16bo$o17bo4bo17bo3$21bo$20bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ ZOOM 8 ]]
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

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  A036987, the Fredholm-Rueppel sequence.

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 input stream with an IBSG coming orthogonally. 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.

Other patterns

Thanks to B2e, the Margolus oscillators as in the black-white reversal of Banks-I exist.

Linear feedback shift registers

Any BSG, with width is 8n+1 generates the output of a Linear Feedback Shift Register. Only numbers from  A123399 generate maximum length LFSRs, and have periods of 2n-1.

The highest number listed is 419 which has a period of 2419-1, about 1.35 x 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,240
53 425 9,007,199,254,740,990

References

  1. ↑ Jeremy Tan (November 30, 2018). Interpreting MCell's "general binary" rule family (discussion thread) at the ConwayLife.com forums
  • Cellular Automata Logic Rule at logic-ca.com (Jan 2005 archive on the Wayback Machine; currently down) - I have all of the files for this web site, but it's not currently hosted anywhere.

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 I 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.