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 |
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, 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]
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