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:

    In history the great moment is, when the savage is just ceasing to be a savage, with all his hairy Pelasgic strength directed on his opening sense of beauty;—and you have Pericles and Phidias,—and not yet passed over into the Corinthian civility. Everything good in nature and in the world is in that moment of transition, when the swarthy juices still flow plentifully from nature, but their astrigency or acridity is got out by ethics and humanity.
    Ralph Waldo Emerson (1803–1882)

    America is the only nation in history which, miraculously, has gone directly from barbarism to degeneration without the usual interval of civilization.
    Attributed to Georges Clemenceau (1841–1929)

    Philosophy of science without history of science is empty; history of science without philosophy of science is blind.
    Imre Lakatos (1922–1974)