Codd's Cellular Automaton - History

History

In the 1940s and 50's, 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 cellular automaton with 29 states, and with it a universal constructor. Codd, building on von Neumann's work, found a simpler machine with eight states. This modified von Neumann's question:

  • What kind of logical organization is necessary for an automaton to be able to reproduce itself?

Three years after Codd's work, Edwin Roger Banks showed a 4-state CA in his PhD thesis that was also capable of universal computation and construction, but again did not implement a self-reproducing machine. John Devore, in his 1973 masters thesis, tweaked Codd's rules to greatly reduce the size of Codd's design, to the extent that it could be implemented in the computers of that time. However, the data tape for self-replication was too long; Devore's original design was later able to complete replication using Golly. Christopher Langton made another tweak to Codd's cellular automaton in 1984 to create Langton's loops, exhibiting self-replication with far fewer cells than that needed for self-reproduction in previous rules, at the cost of removing the ability for universal computation and construction.

Read more about this topic:  Codd's Cellular Automaton

Famous quotes containing the word history:

    History is the present. That’s why every generation writes it anew. But what most people think of as history is its end product, myth.
    —E.L. (Edgar Lawrence)

    The history of persecution is a history of endeavors to cheat nature, to make water run up hill, to twist a rope of sand.
    Ralph Waldo Emerson (1803–1882)

    Gossip is charming! History is merely gossip. But scandal is gossip made tedious by morality.
    Oscar Wilde (1854–1900)