Codd's cellular automaton

From Wikipedia, the free encyclopedia

Codd's cellular automaton is a cellular automaton devised by the British computer scientist Edgar F. Codd in 1968.

[edit] 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.

[edit] 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. In Essays on Cellular Automata, A. W. Burks, ed. (Univ. of Illinois 1968)