A
CellularAutomaton, also known as Wire
World. It was described by
AlexanderKeewatinDewdney in a
ScientificAmerican "Computer Recreations" column.
It allows one to simulate digital logic, using solitary "bits" travelling down "wires" and through "gates".
Needless to say, it supports
TuringComplete computation.
Cells are arranged in a square grid, each with 8 neighbors. Each cell has 4 states:
- Background. Always transitions to Background.
- Head. Always transitions to Tail.
- Tail. Always transitions to Wire.
- Wire. transitions to Wire, unless it has 1 or 2 neighbors in state Head, in which case it transitions to Head.
For example, imagine a field with all cells set to Background except for a line of Wire cells, with a Head and Tail at one end. (This pair is called an "electron".) Thus:
tH.........................
The next states will be:
.tH........................
..tH.......................
...tH......................
If the wire forms a loop, the electron will go round and round. If a wire strand leads off the loop, the electron will split and send pulses down the wire. If 2 pulses arrive at the same time in the same place, they can be arranged to cancel. You can make diodes, latches, AND and OR gates.
A diode, if memory serves, is:
..
..tH.. ....
..
-- AlastairBridgewater
See it at
http://neekatave.com/ca/examples/wirewrld/index.shtml.
There's a brief article at
http://mathworld.wolfram.com/WireWorld.html with some examples
of logic gates and an 8x8 -> 16 multiplier.
Cf:
CellularAutomaton