OCA:Banks-I
|
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.
| 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.
| 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.
| 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
- ↑ PHPBB12345 (September 20, 2016). "Banks" equivalent (discussion thread) at the ConwayLife.com forums
- ↑ Hunting (March 16, 2020). Re: "Banks" equivalent (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (November 1, 2017). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
External links
- Banks, E. R. (1971) Information processing and transmission in cellular automata.
Banks-I at Adam P. Goucher's Catagolue MCell built-in Life rules: Banks at Mirek Wójtowicz's Cellebration page