OCA:Banks-I: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
← Older edit
Confocal (talk | contribs)
9,118 edits
Confocal (talk | contribs)
9,118 edits
Confocal (talk | contribs)
9,118 edits
m links, formatting
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
|reversal = B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678
|reversal = B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678
}}
}}
'''Banks-I''' is an two-state [[cellular automaton]] devised by [[Roger Banks]] in his {{year|1971}} PhD thesis as a simulated model of a universal computer.
'''Banks-I''' is an two-state [[cellular automaton]] devised by [[Roger Banks]] in his {{year|1971}} PhD thesis as a simulated model of a [[universal computer]].


== Rule definition and simulation ==
== Rule definition and simulation ==
Line 15: Line 15:
* Any dead cell with three or four orthogonally adjacent live neighbours comes to life; otherwise it remains dead.
* Any dead cell with three or four orthogonally adjacent live neighbours comes to life; otherwise it remains dead.


In current terminology, what he specified is an [[isotropic non-totalistic cellular automaton]] on the range-1 [[von Neumann neighbourhood]]. Since the neighbourhood is a subset of the [[Moore neighbourhood]], the rule can also be written in Hensel notation. However, the resulted rulestring (B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78)<ref name="post35944" /> is very bulky due to reflecting all of the possible configurations of a cell's diagonally adjacent neighbour.
In current terminology, what he specified is an [[isotropic non-totalistic cellular automaton]] on the range-1 [[von Neumann neighbourhood]]. Since the neighbourhood is a subset of the [[Moore neighbourhood]], the rule can also be written in [[Hensel notation]]. However, the resulted [[rulestring]] ({{nowrap|B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78}})<ref name="post35944" /> is very bulky due to reflecting all of the possible configurations of a cell's diagonally adjacent neighbour.


A way to get around the issue is to consider the diagonal neighbours of a cell only and leave orthogonal ones dead, leading to an equivalent rule B3c4c/S01c2n3c4c where patterns are rotated 45 degrees.<ref name="post91281" />
A way to get around the issue is to consider the diagonal neighbours of a cell only and leave orthogonal ones dead, leading to an equivalent rule {{nowrap|B3c4c/S01c2n3c4c}} where patterns are rotated 45 degrees.<ref name="post91281" />


Banks-I is a built-in "general binary" rule in [[Mirek's Cellebration]], and also a rule table in [[Golly]] that can be loaded via [[RuleLoader]] even before supporting non-totalistic rules.
Banks-I is a built-in "general binary" rule in [[Mirek's Cellebration]], and also a rule table in [[Golly]] that can be loaded via [[RuleLoader]] even before supporting non-totalistic rules.
Line 25: Line 25:


{{EmbedViewer
{{EmbedViewer
|rle = x = 52, y = 56, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
|rle         = x = 52, y = 56, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
o18bo$5ob14o$4ob15o$20o6b5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b
o18bo$5ob14o$4ob15o$20o6b5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b
3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b
3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b
Line 40: Line 40:
obo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o6b5o2b5o2b5o2b5o$
obo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o6b5o2b5o2b5o2b5o$
17ob2o$16ob3o$o5bo12bo!
17ob2o$16ob3o$o5bo12bo!
|position = center
|viewerconfig = #C [[ WIDTH 600 HEIGHT 600 THUMBSIZE 2 ZOOM 8 ]]
|viewerconfig = #C [[ ZOOM 8 WIDTH 600 HEIGHT 600 ]]
|position    = center
|caption = The wire, signal and "dead-end" in all orientations<br>
|caption     = The wire, signal and "dead-end" in all orientations
|style        = width:300px;
}}
}}


Signals can be emitted at regular intervals with a "clock". These devices are essentially [[period]]-2<sup>n</sup> signal [[factory|factories]] driven by [[Rule 90]] [[replicator]] loops.
Signals can be emitted at regular intervals with a "clock". These devices are essentially [[period]]-2{{sup|''n''}} signal [[factory|factories]] driven by [[Rule 90]] [[replicator]] loops.


{{EmbedViewer
{{EmbedViewer
|rle = x = 30, y = 16, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
|rle         = x = 30, y = 16, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
5bo11bo$5b13o$bo3b13o$b17o$3obo12bo$4bo5$9bo19bo$9b21o$bo7b21o$b29o$7o
5bo11bo$5b13o$bo3b13o$b17o$3obo12bo$4bo5$9bo19bo$9b21o$bo7b21o$b29o$7o
bo20bo$8bo!
bo20bo$8bo!
|position = center
|viewerconfig = #C [[ WIDTH 600 HEIGHT 360 THUMBSIZE 2 ZOOM 8 ]]
|viewerconfig = #C [[ ZOOM 8 ]]
|position    = center
|caption = Clocks at period 8 and 16 respectively<br>
|caption     = Clocks at period 8 and 16 respectively
|style        = width:300px;
}}
}}


Line 59: Line 61:


{{EmbedViewer
{{EmbedViewer
|rle = x = 75, y = 28, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
|rle         = x = 75, y = 28, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
14b5o30b5o$15b3o32b3o$15b3o32bobo$15b3o32b2o$15b3o32b3o$15b3o32b3o$15b
14b5o30b5o$15b3o32b3o$15b3o32bobo$15b3o32b2o$15b3o32b3o$15b3o32b3o$15b
3o32b3o$15b3o32b3o$15b3o32b3o$15b3o32b3o$o14b3o32b3o$3ob14o15bo16b3o$
3o32b3o$15b3o32b3o$15b3o32b3o$15b3o32b3o$o14b3o32b3o$3ob14o15bo16b3o$
Line 65: Line 67:
3o28b4o4bo$18b3o30b7o16bo$18b3o30b24o$18b3o30bo6b17o$18b3o37b17o$18b3o
3o28b4o4bo$18b3o30b7o16bo$18b3o30b24o$18b3o30bo6b17o$18b3o37b17o$18b3o
37bo15bo$18b3o$18b3o$18b3o$18b3o$18b3o$17b5o!
37bo15bo$18b3o$18b3o$18b3o$18b3o$18b3o$17b5o!
|position = center
|viewerconfig = #C [[ WIDTH 800 HEIGHT 400 THUMBSIZE 2 ZOOM 8 ]]
|viewerconfig = #C [[ ZOOM 8 WIDTH 800 HEIGHT 400 ]]
|position    = center
|caption = The signal duplicator (left) and reflector (right)<br>
|caption     = The signal duplicator (left) and reflector (right)
|style        = width:300px;
}}
}}


Following these, Boolean logic elements including ANDNOT, NOT and NOR gates have been built, which are sufficient to construct a general purpose computer based on the universal [https://en.wikipedia.org/wiki/NOR_logic NOR logic].
Following these, Boolean logic elements including ANDNOT, NOT and NOR gates have been built, which are sufficient to construct a general purpose computer based on the universal NOR logic.{{refn|group=note|See also [https://en.wikipedia.org/wiki/NOR_logic NOR logic] on Wikipedia}}


With some new observations in {{year|2017}}, [[Peter Naszvadi]] constructed a [[Rule 110]] [[unit cell]] in Banks-I, proving the rule Turing-complete.<ref name="post52584" />
With some new observations in {{year|2017}}, [[Peter Naszvadi]] constructed a [[Rule 110]] [[unit cell]] in Banks-I, proving the rule Turing-complete.<ref name="post52584" />


== Related rules ==
== Related rules ==
The [[black/white reversal]] of Banks-I is B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678, which has a slightly shorter rulestring and corresponds to the diagonal equivalent B2c/S2cn3c4c with patterns rotated 45 degrees. They are related to the [[Life-like cellular automaton]] [[2×2]] due to an infinite family of rectangular oscillators that oscillates according to a [[block cellular automaton]] on the [[Margolus neighbourhood]]. For any oscillator with a 2×(4n) box of alive cells in B36/S125 (2×2), the corresponding oscillator is an [[long|extended]] [[barge]] with 2×(4n) alive cells in B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678, or a rectangle of 2×(4n) dots with every coordinate even in B2c/S2cn3c4c.
The [[black/white reversal]] of Banks-I is {{nowrap|B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678}}, which has a slightly shorter rulestring and corresponds to the diagonal equivalent {{nowrap|B2c/S2cn3c4c}} with patterns rotated 45 degrees.
They are related to the [[Life-like cellular automaton]] {{rl|2×2}} due to an infinite family of rectangular oscillators that oscillates according to a [[block cellular automaton]] on the [[Margolus neighbourhood]].
For any oscillator with a {{times|2|(4''n'')}} box of alive cells in {{nowrap|B36/S125}} (2×2), the corresponding oscillator is an [[long|extended]] [[barge]] with {{times|2|(4''n'')}} alive cells in {{nowrap|B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678}}, or a rectangle of {{times|2|(4''n'')}} dots with every coordinate even in {{nowrap|B2c/S2cn3c4c}}.
 
== Notes ==
<references group=note>
</references>


== References ==
== References ==
<references>
<references>
<ref name="post35944">{{LinkForumThread
<ref name="post35944">{{LinkForumThread
|p          = 35944
|format = ref
|format    = ref
|p      = 35944
|title     = "Banks" equivalent
|title = "Banks" equivalent
|author     = PHPBB12345
|author = PHPBB12345
|date       = September 20, 2016
|date   = September 20, 2016
}}</ref>
<ref name="post52584">{{LinkForumThread
|format = ref
|p      = 52584
|title  = Re: List of the Turing-complete totalistic life-like CA
|author = Peter Naszvadi
|date  = November 1, 2017
}}</ref>
}}</ref>
<ref name="post91281">{{LinkForumThread
<ref name="post91281">{{LinkForumThread
|p          = 91281
|format = ref
|format    = ref
|p      = 91281
|title     = Re: "Banks" equivalent
|title = Re: "Banks" equivalent
|author     = Hunting
|author = Hunting
|date       = March 16, 2020
|date   = March 16, 2020
}}</ref>
<ref name="post52584">{{LinkForumThread
|p          = 52584
|format    = ref
|title      = Re: List of the Turing-complete totalistic life-like CA
|author    = Peter Naszvadi
|date      = November 1, 2017
}}</ref>
}}</ref>
</references>
</references>

Latest revision as of 05:40, 24 May 2023

This article is a stub. You can help LifeWiki by expanding it.
Banks-I
x=64, y = 64, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 ! #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 012-e3-ajk4-akqw5-ajk6-e78/3e4ejr5cinqy6-ei78
B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
Character Stable
Black/white reversal B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678

Banks-I is an two-state cellular automaton devised by Roger Banks in his 1971 PhD thesis as a simulated model of a universal computer.

Rule definition and simulation

The original definition of Banks-I by Banks was written in a checkerboard manner and had three rotationally symmetric transition rules, namely:

  • Any live cell with two closest orthogonally adjacent live neighbours dies; otherwise it remains alive.
  • Any dead cell with three or four orthogonally adjacent live neighbours comes to life; otherwise it remains dead.

In current terminology, what he specified is an isotropic non-totalistic cellular automaton on the range-1 von Neumann neighbourhood. Since the neighbourhood is a subset of the Moore neighbourhood, the rule can also be written in Hensel notation. However, the resulted rulestring (B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78)[1] is very bulky due to reflecting all of the possible configurations of a cell's diagonally adjacent neighbour.

A way to get around the issue is to consider the diagonal neighbours of a cell only and leave orthogonal ones dead, leading to an equivalent rule B3c4c/S01c2n3c4c where patterns are rotated 45 degrees.[2]

Banks-I is a built-in "general binary" rule in Mirek's Cellebration, and also a rule table in Golly that can be loaded via RuleLoader even before supporting non-totalistic rules.

Constructions

In the PhD thesis, Banks demonstrated how signal circuitry can be built in Banks-I. A "wire" consists of a three-cell-thick block of live cells, and a "signal" is carried by a duoplet-shaped perturbation travelling at lightspeed along the edge of a wire. A five-cell bump extension and an additional cell on the edge can kill a signal.

x = 52, y = 56, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 o18bo$5ob14o$4ob15o$20o6b5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b 3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b 3o4b2o$16ob3o7b3o4b3o4b3o4b3o$20o7b3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b 3o$27b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o7b3o4b 3o4b3o4b3o$4ob15o7b3o4b3o4b3o4b3o$5ob14o7b3o4b3o4b3o4b3o$o18bo7b3o4b3o 4b2o5b3o$28b2o4b3o4bobo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$ 20o6b5o2b5o2b5o2b5o$17ob2o$16ob3o$o18bo5$o13bo4bo$5ob14o$4ob15o$20o6b 5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b 3o$o6bo11bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b4o3b2o$16ob3o7b3o4b3o4b 3o4b3o$20o6b4o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$27b 3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o7b3o4b3o4b3o4b3o$4ob15o7b3o3b 4o4b3o4b4o$5ob14o7b3o4b3o4b3o4b3o$o12bo5bo7b3o4b3o4b2o5b3o$28b2o4b3o4b obo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o6b5o2b5o2b5o2b5o$ 17ob2o$16ob3o$o5bo12bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ WIDTH 600 HEIGHT 600 THUMBSIZE 2 ZOOM 8 ]]
The wire, signal and "dead-end" in all orientations
(click above to open LifeViewer)

Signals can be emitted at regular intervals with a "clock". These devices are essentially period-2n signal factories driven by Rule 90 replicator loops.

x = 30, y = 16, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 5bo11bo$5b13o$bo3b13o$b17o$3obo12bo$4bo5$9bo19bo$9b21o$bo7b21o$b29o$7o bo20bo$8bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ WIDTH 600 HEIGHT 360 THUMBSIZE 2 ZOOM 8 ]]
Clocks at period 8 and 16 respectively
(click above to open LifeViewer)

A lone signal can be duplicated when passing a fanout junction, or reflected 90 degrees.

x = 75, y = 28, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 14b5o30b5o$15b3o32b3o$15b3o32bobo$15b3o32b2o$15b3o32b3o$15b3o32b3o$15b 3o32b3o$15b3o32b3o$15b3o32b3o$15b3o32b3o$o14b3o32b3o$3ob14o15bo16b3o$ 2ob31o16b3o$15o3b16o15b4o$o12b2o3b16o16b3o$13b2o3b3o12bo16b3o$12b4o2b 3o28b4o4bo$18b3o30b7o16bo$18b3o30b24o$18b3o30bo6b17o$18b3o37b17o$18b3o 37bo15bo$18b3o$18b3o$18b3o$18b3o$18b3o$17b5o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ WIDTH 800 HEIGHT 400 THUMBSIZE 2 ZOOM 8 ]]
The signal duplicator (left) and reflector (right)
(click above to open LifeViewer)

Following these, Boolean logic elements including ANDNOT, NOT and NOR gates have been built, which are sufficient to construct a general purpose computer based on the universal NOR logic.[note 1]

With some new observations in 2017, Peter Naszvadi constructed a Rule 110 unit cell in Banks-I, proving the rule Turing-complete.[3]

The black/white reversal of Banks-I is B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678, which has a slightly shorter rulestring and corresponds to the diagonal equivalent B2c/S2cn3c4c with patterns rotated 45 degrees. They are related to the Life-like cellular automaton 2×2 due to an infinite family of rectangular oscillators that oscillates according to a block cellular automaton on the Margolus neighbourhood. For any oscillator with a 2 × (4n) box of alive cells in B36/S125 (2×2), the corresponding oscillator is an extended barge with 2 × (4n) alive cells in B2e3ajk4akqw5ajk6e/S2ei3aejkr4-cny5-e678, or a rectangle of 2 × (4n) dots with every coordinate even in B2c/S2cn3c4c.

Notes

  1. ↑ See also NOR logic on Wikipedia

References

  1. ↑ PHPBB12345 (September 20, 2016). "Banks" equivalent (discussion thread) at the ConwayLife.com forums
  2. ↑ Hunting (March 16, 2020). Re: "Banks" equivalent (discussion thread) at the ConwayLife.com forums
  3. ↑ Peter Naszvadi (November 1, 2017). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
Retrieved from "https://conwaylife.com/w/index.php?title=OCA:Banks-I&oldid=131389"