OCA:Banks-I

From LifeWiki
(Redirected from Banks-I)
Jump to navigation Jump to search
Radiation.png This article is a stub. You can help LifeWiki by expanding it.


Banks-I
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 Life-like 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 [[ ZOOM 8 WIDTH 600 HEIGHT 600 ]]
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 [[ 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 [[ ZOOM 8 WIDTH 800 HEIGHT 400 ]]
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.

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

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

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

External links