Definitions

Codd's cellular automaton

Codd's cellular automaton

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

Search another word or see Codd's Cellular Automatonon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;