Article on other languages:
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
 |
The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. |
Codd's cellular automaton is a cellular automaton devised by the British computer scientist Edgar F. Codd in 1968.
Motivation
In the 1940s, John von Neumann posed the following problem:
- What kind of logical organization is sufficient for an automaton to be able to reproduce itself?
He was able to construct a Universal Constructor with a square grid and 29 states. E.F. Codd found a simpler machine with only eight states. Therefore von Neumann's question had to be modified:
- What kind of logical organization is necessary for an automaton to be able to reproduce itself?
Codd's cellular automaton is an 8-state, 5-neighbor cellular automaton. Its main concept is based on (1-)paths on the empty (0-)field. These paths are wires for signals consisting of one of the numbers 4 to 7 followed by a single 0 to define the direction of transmission. To prevent signals from flooding into the 0-space, every path is sheathed by a line of 2-states on each side. (This basic organization is shared by many cellular automata, such as Wireworld.)
Christopher Langton presented a simplification of Codd's cellular automaton in 1984; that automaton, called Langton's loops, also exhibits reproductive behavior.
References
- E. F. Codd, Cellular Automata (Academic Press, New York, 1968)
- Christopher G. Langton, Self-Reproduction in Cellular Automata, Physica 10D (1984)
- J. v. Neumann, "The Theory of Self-Reproducing Automata". Essays on Cellular Automata, A. W. Burks, ed. (Univ. of Illinois 1968)
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
