Codd's cellular automaton is a cellular automaton (CA) devised by the Britishcomputer scientistEdgar F. Codd in 1968. It was designed to recreate the computation- and construction-universality of von Neumann's CA but with fewer states: 8 instead of 29. Codd showed that it was possible to make a self-reproducing machine in his CA, in a similar way to von Neumann's universal constructor, but never gave a complete implementation.
A simple configuration in Codd's cellular automaton. Signals pass along wire made of cells in state 1 (blue) sheathed by cells in state 2 (red). Two signal trains circulate around a loop and are duplicated at a T-junction onto an open-ended section of wire. The first (7-0) causes the sheathed end of the wire to become exposed. The second (6-0) re-sheathes the exposed end, leaving the wire one cell longer than before.
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.[2] 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.[3] 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.[4]
The construction arm in Codd's CA can be moved into position using the commands listed in the text. Here the arm turns left, then right, then writes a cell before retracting along the same path.
The table below shows the signal-trains needed to accomplish different tasks. Some of the signal trains need to be separated by two blanks (state 1) on the wire to avoid interference, so the 'extend' signal-train used in the image at the top appears here as '70116011'.
purpose
signal train
extend
70116011
extend_left
4011401150116011
extend_right
5011501140116011
retract
4011501160116011
retract_left
5011601160116011
retract_right
4011601160116011
mark
701160114011501170116011
erase
601170114011501160116011
sense
70117011
cap
40116011
inject_sheath
701150116011
inject_trigger
60117011701160116011
Universal computer-constructor
Codd designed a self-replicating computer in the cellular automaton, based on Wang's W-machine. However, the design was so colossal that it evaded implementation until 2009, when Tim Hutton constructed an explicit configuration.[5] There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.
codd, cellular, automaton, cellular, automaton, devised, british, computer, scientist, edgar, codd, 1968, designed, recreate, computation, construction, universality, neumann, with, fewer, states, instead, codd, showed, that, possible, make, self, reproducing,. Codd s cellular automaton is a cellular automaton CA devised by the British computer scientist Edgar F Codd in 1968 It was designed to recreate the computation and construction universality of von Neumann s CA but with fewer states 8 instead of 29 Codd showed that it was possible to make a self reproducing machine in his CA in a similar way to von Neumann s universal constructor but never gave a complete implementation A simple configuration in Codd s cellular automaton Signals pass along wire made of cells in state 1 blue sheathed by cells in state 2 red Two signal trains circulate around a loop and are duplicated at a T junction onto an open ended section of wire The first 7 0 causes the sheathed end of the wire to become exposed The second 6 0 re sheathes the exposed end leaving the wire one cell longer than before Contents 1 History 1 1 Comparison of CA rulesets 2 Specification 3 Universal computer constructor 4 See also 5 References 6 External linksHistory EditIn the 1940s and 50s John von Neumann posed the following problem 1 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 2 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 3 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 4 Comparison of CA rulesets Edit CA number of states symmetries computation and construction universal size of self reproducing machinevon Neumann 29 none yes 130 622 cellsCodd 8 rotations yes 283 126 588 cells 5 Devore 8 rotations yes 94 794 cellsBanks IV Banks IV Cellular Automaton 2 4 6 3 rotations and reflections yes Somewhere around 100 000 000 000 cellsLangton s loops 8 rotations no 86 cellsSpecification Edit The construction arm in Codd s CA can be moved into position using the commands listed in the text Here the arm turns left then right then writes a cell before retracting along the same path Codd s CA has eight states determined by a von Neumann neighborhood with rotational symmetry The table below shows the signal trains needed to accomplish different tasks Some of the signal trains need to be separated by two blanks state 1 on the wire to avoid interference so the extend signal train used in the image at the top appears here as 70116011 purpose signal trainextend 70116011extend left 4011401150116011extend right 5011501140116011retract 4011501160116011retract left 5011601160116011retract right 4011601160116011mark 701160114011501170116011erase 601170114011501160116011sense 70117011cap 40116011inject sheath 701150116011inject trigger 60117011701160116011Universal computer constructor EditCodd designed a self replicating computer in the cellular automaton based on Wang s W machine However the design was so colossal that it evaded implementation until 2009 when Tim Hutton constructed an explicit configuration 5 There were some minor errors in Codd s design so Hutton s implementation differs slightly in both the configuration and the ruleset See also EditArtificial life Cellular automaton Conway s Game of Life Langton s loops Von Neumann cellular automaton WireworldReferences Edit von Neumann John Burks Arthur W 1966 Theory of Self Reproducing Automata www walenz org Archived from the original on 2008 01 05 Retrieved 2012 01 28 Codd Edgar F 1968 Cellular Automata Academic Press New York a b Banks Edwin 1971 Information Processing and Transmission in Cellular Automata PhD thesis MIT Department of Mechanical Engineering Langton C G 1984 Self Reproduction in Cellular Automata PDF Physica D Nonlinear Phenomena 10 1 2 135 144 Bibcode 1984PhyD 10 135L doi 10 1016 0167 2789 84 90256 2 hdl 2027 42 24968 a b Hutton Tim J 2010 Codd s self replicating computer PDF Artificial Life 16 2 99 117 doi 10 1162 artl 2010 16 2 16200 PMID 20067401 S2CID 10049331 Roger Banks Proof of Universal Computation in Cellular Automata External links EditThe Rule Table Repository has the transition table for Codd s CA Golly supports Codd s CA along with the Game of Life and other rulesets Download the complete machine 13MB and more details 1 shows more on Banks IV Retrieved from https en wikipedia org w index php title Codd 27s cellular automaton amp oldid 1096366474, wikipedia, wiki, book, books, library,
