| The Cellular Automata of John von Neumann
The crossing problem in JVN automata
In the JVN automata environment (JVN transition rules), the transmission lines are used to propagate sequences of excited and unexcited transmission states (activation pulses) briefly called activation trains. Two or more transmission lines can be combined, with the possible interposition of confluent states, to implement the logical AND, the logical OR as well as activation train bifurcations or trifurcations. Unfortunately, the transition rules planned by von Neumann do not permit simple implementations of activation-train crossings. Von Neumann himself described the structure represented here below
as the simplest cell assembly capable of performing the crossing function. It includes several excited states, among which there are 10 excited confluent states (enlightened diamonds) playing the role of one-bit memories. You can analyze in detail the behavior of this cell assembly by loading and running the file CROSSINGS.JVN from the folder JVN. Unfortunately, this sort of crossing cannot be used in construction processes as, to avoid unpredictable behaviors, constructing arms are allowed to generate only quiescent cell-states.
To circumvent this difficulty, von Neumann designed a sort of multiplexer formed by an array of coders in series with a set of decoders. The latters behave as filters of the activation trains arriving from the formers via a multiply bifurcated transmission line. The coders translate single activation pulses into specific activation trains, which are then transmitted to all the decoders. Each decoder translates a specific activation train into a single activation pulse annihilating all the others. Providing that the activation trains travel sufficiently far apart from each other along the connecting line, a set of sufficiently sparse activation pulses inputted to the coder array result into a differently ordered set of sparse activation pulses exiting from the output lines of the decoders. The figure here below provides an example of a crossing device multiplexing two transmission lines via a decoder-coder pair.
The coder on the top-left translates an activation pulse inputted at A to an activation train represented by the binary sequence 10011 (shown by the red-arrow sequence shown above the coder output line). This activation train, which is filtered by the decoder on the bottom-right, results into a single activation pulse released by A'. The same activation train is instead annihilated by the decoder on the top-right. In a similar way, a pulse inputted to B is coded by the coder on the bottom-left to the activation train of binary sequence 10101 (red arrow sequence below). Once filtered by the decoder on the top-right, this activation train results into an activation pulse exiting from B'. The same activation train is instead annihilated by the decoder on the bottom-right.
Examples of ordinary transmission lines crossings by the multiplexing method are found (only with JVN transition rules) in folder JVN as JVN_CROSSING.JVN, 7_MULTIPLEXER.JVN, 7_MULTIPLEXER.JFR.
Clearly, since a self-reproducing automaton requires the crossing of several activation trains, the implementation of crossings by the multiplexing method increases considerably automaton complexity. More unpleasantly, encoding messages as trains of sparse activation pulses slackens the signal traffic very heavily. In Author's experiance, the implementation of self-reproducing automata with JVN transition rules appeared to be prohibitively hard. This is the reason why in 1994 the Author decided to extend the transition rules proposed by von Neumann (JVN transition rules) by adding three new excitation levels to the confluent state and by modifying accordingly the rules, which were then called extended von Neumann (EVN) transition rules. The file CROSSINGS.EVN (in folder EVN) provides examples of multiple crossings in the EVN automata environment.
Different behaviors of the JVN and the EVN confluent state
In the environment of JVN transition rules, the confluent state provides the following functions:
- One-step delayed bifurcations of an incoming blue line (ordinary transmission line) into 1, 2 or 3 outgoing blue lines or red lines (special transmission lines).
- One-step delayed logical AND of two incoming blue lines into 1 or 2 outgoing blue or red lines, or of 3 incoming blue lines into 1 outgoing blue or red line.
In the environment of EVN transition rules, it provides the following functions:
- One-step delayed bifurcations of one incoming blue line into 1, 2 or 3 outgoing blue lines or red lines.
- One-step delayed logical AND of two incoming blue lines into 1 outgoing blue or red line or of 3 incoming blue lines into 1 outgoing blue or red line, but not of 2 incoming blue lines into 2 outgoing blue or red lines.
- Undelayed crossing of 2 incoming blue lines and 2 outgoing blue or red lines.
- One-bit memory.
To perform the latter function, the confluent state must be the terminal state of a blue line. The bit is stored as an excitation level of the confluent state. To retrieve a previously stored bit, a blue or red outgoing arrow must be suitably created in the nearest neighbor. As soon as this is done, the confluent state transits trough the sequence next-excited, exited-next-excited and quiescent state, and transmits its excitation to the outgoing arrow with one-step delay.
The behavior of the confluent state in EVN activation train crossings is exemplified in CROSSINGS.EVN.