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 in 1987, as part of his program Phantom Fish Tank. It subsequently became more widely known as a result of an article in the "Computer Recreations" column of ''
Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it, with more than 150 Nobel Pri ...
''.
Wireworld is particularly suited to simulating
transistor
A transistor is a semiconductor device used to Electronic amplifier, amplify or electronic switch, switch electrical signals and electric power, power. It is one of the basic building blocks of modern electronics. It is composed of semicondu ...
s, and is
Turing-complete
In computability theory, a system of data-manipulation rules (such as a model of computation, 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 ...
.
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 aut ...
, 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 a device that performs 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, one that has, for ...
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 model of computation, 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 ...
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 chrestomathy website with implementations of common algorithms and solutions to various computer programming, programming problems in many different programming languages. It is named for the Rosetta Stone ...
The Wireworld computer in Java
Cellular automaton rules