Lecture
The von Neumann cellular automaton — a cellular automaton developed by von Neumann with the assistance of Stanislaw Ulam to investigate the possibility of creating self-reproducing machines.
One of the simple configurations in the von Neumann cellular automaton. A binary signal circulates along a loop of blue cells, using the transition between the ordinary and excited state of the transmission cells. A switching cell duplicates the signal into a red line consisting of cells in a special transmission state. The signal travels along the line and creates a new cell. The binary signal 1011 encodes an east-oriented transmission state, thereby continuing the line to the right. In the process of creation, the new cell, controlled by the binary sequence, passes through a series of sensitised states.
A cellular automaton, in general form, represents an ordered set of finite automata exchanging information with neighbouring automata. In the von Neumann cellular automaton the cells are arranged as a two-dimensional rectangular lattice and interact with the four immediately adjacent cells that form the von Neumann neighbourhood. The lattice is considered to be of infinite size in both directions, and the cells are identical with respect to their transition rules. The states of all cells change synchronously.
Each finite automaton in the von Neumann space can take one of 29 states:
Each of the transmission states (8 states) is also characterised by being excited/unexcited (green/blue arrows), which gives 16 transmission states in total. The excited state carries data at a rate of 1 bit per clock cycle. Confluent states have a delay of one clock cycle, and can thus store 2 bits of information.
The flow of information between cells is determined by the directionality property. The following rules apply:
The following rules apply to confluent states:
Nine types of cells that can be created in the von Neumann CA. Here binary signals travel along ordinary transmission cells, creating new cells at the ends of the lines. For example, the binary string 1011, shown on the fifth line, creates a special transmission state with a rightward direction. There is no interaction between transmission lines, which allows the cells to be packed densely.
In the initial state, most of the cellular space is «empty», that is, filled with cells in the state U. Having received an input signal from a transmission cell, the neighbouring cell in state U switches to a transient state, passes through a series of states, and ends up in one of the transmission or confluent states. This final state is determined by the sequence of input signals. That is, transient states can be regarded as bifurcation points on the path from the ground state to the transmission and confluent states. In the following rules the sequence of input signals is indicated in brackets as a binary string:
Approximately 4000 bits of data construct a complex pattern. Here a variant of the von Neumann CA with 32 states, known as Hutton32, is used.
One of the variants of the von Neumann automaton is the Nobili automaton, in which additional states are introduced to provide memory and the ability for signals to cross without interference, for which purpose the capability of storing information across groups of cells is used. The latter function requires three additional states, as a result of which the Nobili automaton has 32 states rather than 29. It is the invention of Renato Nobili (Italian: Renato Nobili), a professor of physics at the University of Padua, Italy. Von Neumann deliberately excluded states intended for signal crossing.
The confluent state is modified so as to transmit two simultaneously arriving signals independently of one another, or to store and transmit input signals with a delay.
Yet another variant is the Hutton automaton (English: Hutton), which allows the replication of ring structures (see Langton's loops in English).
The Nobili cellular automaton — a variant of the von Neumann cellular automaton, into which additional states are introduced to provide memory and the ability for signals to cross without interference. It is the invention of Renato Nobili, a professor of physics at the University of Padua, Italy. Von Neumann deliberately excluded states intended for signal crossing.
The confluent state is modified so as to transmit two simultaneously arriving signals independently of one another, or to store and transmit input signals with a delay.
λ G , the minimal self-reproducing configuration in Nobili cellular automata
Nobili cellular automata (NCA) represent a variant of von Neumann cellular automata (vNCA), in which additional states provide means of memory and unimpeded signal crossing. Nobili cellular automata are the invention of Renato Nobili, a professor of physics at the University of Padua, Italy. Von Neumann specifically excluded the use of states intended for signal crossing.
The confluent state is modified so that it acts as an organ that crosses a signal if exactly two signal paths meet (they enter and exit the confluent state), or acts as a memory organ if only inputs exist.
The advantage of these changes to the set of states of the von Neumann cellular automaton is that signal crossing is considerably simplified, configurations are somewhat smaller than the corresponding configuration in von Neumann cellular automata, and computational performance is increased.
In the original von Neumann cellular automaton, signal crossing is much more complex. The most widely used signal-crossing organs are the coded channel (developed 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 able to freely cross entire packets, similar to the crossing organ in Nobili's cellular automaton. The Mukhopadhyay crossing organ consists of three XOR gates, as shown (left).
Diagram of the Mukhopadhyay crossing organ, showing three exclusive-OR gates.
In Nobili's cellular automaton, the organ that crosses a signal consists of a single confluent cell with two perpendicular input paths and two perpendicular output paths. Because of its significantly reduced size (compared with any of the vNCA crossing organs), self-reproducing machines in NCA are much more compact. For example, the smallest replicator to date, λ G , comprises only 485 somatic cells.
Memory can be stored in vNCA in several ways. One of them (the electronic method) consists in creating a loop of OTS cells, around which an excited pulse travels. The most common method (the electromechanical method) is to use a special transmission state to create and delete an ordinary transmission state, which acts as a gate. Minor modifications can give rise to many different gates, including latches, pulse dividers and one-shot gates.
In Nobili's cellular automaton this task is likewise simplified. A confluent cell with no outputs «holds» the excitation pulse until an output is created. In the λ G diagram above, an excited confluent cell is shown in orange. It will remain in this state until a neighbouring OTS cell is created, after which the information will flow into the next confluent cell.
Comments