Wireworld, alternatively WireWorld, is a
cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
first proposed by
Brian Silverman
Brian Silverman is a Canadian computer scientist, the creator of many programming environments for children,[Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...](_blank)
''.
Wireworld is particularly suited to simulating
transistor
upright=1.4, gate (G), body (B), source (S) and drain (D) terminals. The gate is separated from the body by an insulating layer (pink).
A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch e ...
s, and is
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
.
Rules
A Wireworld cell can be in one of four different states, usually numbered 0–3 in software, modeled by colors in the examples here:
- empty (black),
- electron head (blue),
- electron tail (red),
- conductor (yellow).
As in all cellular automata, time proceeds in discrete steps called generations (sometimes "gens" or "ticks"). Cells behave as follows:
* empty → empty,
* electron head → electron tail,
* electron tail → conductor,
* conductor → electron head if exactly one or two of the neighbouring cells are electron heads, otherwise remains conductor.
Wireworld uses what is called the
Moore neighborhood
In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice and is composed of a central cell and the eight cells that surround it.
Name
The neighborhood is named after Edward F. Moore, a pioneer of cellular au ...
, which means that in the rules above, neighbouring means one cell away (range value of one) in any direction, both orthogonal and diagonal.
These simple rules can be used to construct
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
s (see below).
Applications
Entities built within Wireworld universes include
Langton's Ant (allowing any Langton's Ant pattern to be built within Wireworld) and the Wireworld computer, a
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
computer implemented as a cellular automaton.
See also
*
von Neumann's cellular automaton
References
{{Reflist
External links
Wireworldon
Rosetta Code
Rosetta Code is a wiki-based programming website with implementations of common algorithms and solutions to various programming problems in many different programming languages. It is named for the Rosetta Stone, which has the same text inscribe ...
The Wireworld computer in JavaNo Wires(contains an interactive Wireworld widget)
Cellular automaton rules