OCA:Logic Rule: Difference between revisions
DavidConant (talk | contribs) |
DavidConant (talk | contribs) |
||
| Line 130: | Line 130: | ||
{{LinkCatagolueRule|b2aes|rulename=LogicRule}} | {{LinkCatagolueRule|b2aes|rulename=LogicRule}} | ||
{{LinkMirek|rullex_gebi.html#LogicRule|title=MCell built-in General binary rules: LogicRule}} | {{LinkMirek|rullex_gebi.html#LogicRule|title=MCell built-in General binary rules: LogicRule}} | ||
* [https://docs.google.com/spreadsheets/d/1z6mX6dWofmo7KwOuY-4U-ixorAnaTdfZtAPwCcs-_gY/edit Google spreadsheet | * [https://docs.google.com/spreadsheets/d/1z6mX6dWofmo7KwOuY-4U-ixorAnaTdfZtAPwCcs-_gY/edit BSG info] Google spreadsheet | ||
* [https://drive.google.com/file/d/1bOS52ssJ_yo2UFBwNVktexf04eUlsm4-/view?usp=sharing 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. | * [https://drive.google.com/file/d/1bOS52ssJ_yo2UFBwNVktexf04eUlsm4-/view?usp=sharing 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. | ||
* [https://drive.google.com/file/d/1UMSTvG-z0h5Pf0RVrznSGAHDtZpihrJY/view?usp=sharing BSG.c] Original C program used to generate output and period. | * [https://drive.google.com/file/d/1UMSTvG-z0h5Pf0RVrznSGAHDtZpihrJY/view?usp=sharing BSG.c] Original C program used to generate output and period. | ||
Revision as of 23:47, 17 August 2021
| This article is a stub. You can help LifeWiki by expanding it. |
| Logic Rule | |
| 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).
| 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 | ||
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.
References
- ↑ Jeremy Tan (November 30, 2018). Interpreting MCell's "general binary" rule family (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) - 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.