Nobili cellular automata

λ_G, a minimal self-replicating configuration in Nobili cellular automata

Nobili cellular automata are a variation of von Neumann cellular automata, in which additional states provide means of memory and the interference-free crossing of signal. Nobili cellular automata are the invention of Renato Nobili, a professor of physics at the University of Padova in Padova, Italy. Von Neumann specifically excluded the use of states dedicated to the crossing of signal.

The confluent state is altered, so that it acts as a signal crossing organ if exactly two signal paths are incident (they enter and leave the confluent state), or acts as a memory organ if only inputs exist.

The benefit of these alterations to the state set of von Neumann cellular automata is that signal crossing is greatly eased, configurations are slightly smaller than the corresponding configuration of von Neumann cellular automata, and the computational throughput is increased.

Signal crossing in vNCA

In von Neumann's original cellular automaton, the crossing of signals is much more difficult. The most widely used signal crossing organs are the coded channel (devised by von Neumann himself), Gorman's real-time crossing organ, and the Mukhopadhyay crossing organ. The coded channel can only cross individual pulses; the others are capable of crossing entire packets without interference, analogous the crossing organ in Nobili's cellular automaton. The Mukhopadhyay crossing organ comprises three XOR gates, in the arrangement shown (left).

Schematic of the Mukhopadhyay crossing organ, showing the three exclusive-or gates.

Signal crossing in NCA

In Nobili cellular automaton, a signal crossing organ consists of a single confluent cell, with two perpendicular input paths and two perpendicular output paths. Due to the substantially reduced size (as compared with any of the vNCA crossing organs), self-replicating machines are much more compact in NCA. For example, the smallest replicator so far, λ_G, comprises only 485 somatic cells.

Memory storage in vNCA

Storing memory in vNCA can be done in multiple ways. One of these (the electronic method) is to create a loop of OTS cells with an excited pulse travelling around it. By far the most common way (the electro-mechanical method) is to use a special transmission state to construct and delete an ordinary transmission state, to act as a gate. Slight modifications can yield a plethora of different gates, including latches, pulse dividers, and one-time gates.

Memory storage in NCA

In Nobili's cellular automaton, this task is also simplified. A confluent cell with no outputs 'holds' a pulse of excitation until an output is created. In the diagram of λ_G (above, right), the excited confluent cell is displayed in orange. It will remain in this state until an adjacent OTS cell is created, at which point the information will flow into the next confluent cell.

References

• Buckley, W. R. Signal Crossing Solutions in von Neumann self-replicating cellular automata (Automata 2008).