Interestingly, qualitative categories of replicator such as ‘universal constructor’, ‘loop’, and ‘parity-rule replicator’ form visually distinct clusters in the space: We can plot the population count (including the tape) of different self-replicating machines on one axis, and the complexity of the rule on the other axis. Conway’s two-state rule, by comparison, has only 18 bits of complexity. įor instance, Langton’s, Codd’s and Chou-Reggia’s cellular automata all have a complexity of 25056 bits, whereas Nobili’s 32-state adaptation of von Neumann’s original 29-state rule has a complexity of 167772160 bits. (We get equality in the case of asymmetric rules, but for rules with symmetries the count is more complex and depends on the Polya Enumeration Theorem.) Consequently, we can concretely define the ‘complexity’ of the rule (in bits) to be. Comparison of replicatorsįor an n-state k-neighbour cellular automaton, there are different rules, where is the number of distinct neighbourhoods that can occur. Tim Hutton’s implementation of Codd’s self-replicating computerĬodd’s cellular automaton itself was borne out of a bet in a pub, where Codd challenged a friend that he could create a self-replicating computer in a cellular automaton with fewer states than von Neumann’s original 29-state cellular automaton. It took until 2010 before Codd’s machine was actually built, with some slight corrections, by Tim Hutton. Codd’s cellular automaton was designed to support universal computers augmented with universal construction capabilities: unlike Langton’s loops, the instruction tape can program the machine to build any configuration of quiescent cells, not just a simple copy of itself. Codd (the inventor of the relational database). The inspiration for Langton’s loop was an earlier (1968) 8-state cellular automaton by E. However, every configuration in that rule replicates, including a photograph of Fredkin, so it is hard to claim that this is self-directed. If minimality were the only concern, all of these examples would be blown out of the water by Edward Fredkin’s single-cell replicator in the 2-state XOR rule.
The loops, which are barely recognisable as such, are only 6 cells in size: half of Byl’s loop and an order of magnitude smaller than Langton’s. In 1993, Chou and Reggia removed the outer sheath from the loop by adding two more states (returning to 8, same as Langton).
This comes at the expense of reduced flexibility whereas one could build a larger Langton’s loop by increasing each side-length by n and inserting n ‘move forward’ instructions into the loop, there is no way to construct a Byl loop with any other genome. Moreover, the underlying rule is simpler: only 6 states instead of 8.
0 kommentar(er)
