Automaton von Neumann

Configuration

In general, a cellular automaton is an ordered set of finite automata that exchange information with neighboring automata. In a von Neumann cellular automaton, cells are ordered in the form of a two-dimensional rectangular lattice and interact with four directly adjacent cells that form a von Neumann neighborhood . The lattice is considered to have infinite size in both directions, and the cells are identical in terms of transition rules. The change of states of all cells occurs synchronously.

States

Each finite state machine in von Neumann space can take one of 29 states:

1. base state U
2. transit (or sensitive) states
   1. S
   2. S ₀
   3. S ₀₀
   4. S ₀₁
   5. S ₀₀₀
   6. S ₁
   7. S ₁₀
   8. S ₁₁
3. confluent conditions
   1. C ₀₀
   2. C ₁₀
   3. C ₀₁
   4. C ₁₁
4. normal transmitting state
   1. T ₀₀ right
   2. T ₀₁ up
   3. T ₀₂ left
   4. T ₀₃ down
5. special transmitting state
   1. T ₁₀ right
   2. T ₁₁ up
   3. T ₁₂ left
   4. T ₁₃ down

Each of the transmitting states (8 states) is also characterized by excitement / non-excitation (green / blue arrows), which results in 16 transmitting states. An excited state transfers data at a rate of 1 bit per clock. Confluent states have a delay of one clock cycle, and thus can store 2 bits of information.

Transition State Transition Rules

The flow of information between cells is determined by the directivity property. The following rules apply:

• The transmitting states apply the OR operator to the input signals, that is, the cell in the transmitting state (normal or special) will go into the excited state at step t + 1 if any of the input signals is excited at the step t
• States are transmitted between transmitting cells according to the directivity property.
• Ordinary and special transmitting conditions are "antagonists":
  • If cell A at measure t in a normal excited transmitting state points to cell B in any special transmitting state, then at measure t + 1, cell B will go to the base state U. The special transmitting state will be “destroyed”.
  • A similar event will occur if a cell in a special transmitting state points to a normal transmitting cell.

Confluent State Transition Rules

The following rules apply to confluent states:

• Confluent cells do not transmit data among themselves.
• Confluent cells receive input from one or more ordinary transmitting cells and issue them to transmitting cells (regular or special) that do not indicate the current cell.
• Data is not transmitted in the direction opposite to the direction of the transmitting cell.
• Data stored by the confluent cell is lost if it does not have adjacent transmitting cells (not pointing to it).
• Confluent cells serve as bridges between conventional and special transmitting cells.
• Confluent cells apply the AND operator to input signals.
• Confluent cells delay the signal by one cycle longer than conventional transmitting cells.

Transition State Transition Rules

In the initial state, most of the cell space is "empty", that is, filled with cells in the U state. Having received the input signal from the transmitting cell, the neighboring cell in the U state goes into a transit state, passes a series of states, and ends up in one of the transmitting or confluent states. This final state is determined by the sequence of input signals. That is, transit states can be considered as bifurcation points on the way from the base state to the transmitting and confluent ones. In the following rules, the input signal sequence is shown in brackets with a binary string:

• a cell in the base state U , having received a signal, goes into state S (1)
• a cell in state S , having not received a signal, goes into state S ₀ (10)
  • a cell in state S ₀ , without receiving a signal, goes to S ₀₀ (100)
    • cell S ₀₀ , not receiving a signal, goes to S ₀₀₀ (1000)
      • cell S ₀₀₀ , not receiving a signal, goes to T ₀₀ (10000)
      • cell S ₀₀₀ , having received the signal, goes to T ₀₁ (10001)
    • cell S ₀₀ , having received the signal, goes to T ₀₂ (1001)
  • cell S ₀ , having received the signal, goes to S ₀₁ (101)
    • cell S ₀₁ , not receiving a signal, goes to T ₀₃ (1010)
    • cell S ₀₁ , having received the signal, goes to T ₁₀ (1011)
• cell S , having received the signal, goes to S ₁ (11)
  • cell S ₁ , not receiving a signal, goes to S ₁₀ (110)
    • cell S ₁₀ , not receiving a signal, goes to T ₁₁ (1100)
    • cell S ₁₀ , having received the signal, goes to T ₁₂ (1101)
  • cell S ₁ , having received the signal, goes to S ₁₁ (111)
    • cell S ₁₁ , not receiving a signal, goes to T ₁₃ (1110)
    • cell S ₁₁ , having received the signal, goes to C ₀₀ (1111)

Destructive Rules

• The input signal from a special transmitting cell, received by the cell in a confluent or normal transmitting state, transfers this cell to the base one.
• The input signal from a conventional transmitting cell received by a special transmitting cell transfers this cell to the base one.

One of the varieties of the von Neumann automaton is the Nobili automaton , in which additional states are introduced to provide memory and the possibility of crossing signals without interference, for which the possibility of storing information by groups of cells was used. The latter function requires three additional states, whereby the Nobili automaton has 32 states, not 29. It is an invention of Renato Nobili ( Italian: Renato Nobili ), a professor of physics at the University of Padova , Italy . Von Neumann intentionally ruled out states designed to cross signals.

The confluent state is changed in such a way as to transmit two simultaneously incoming signals independently from each other, or to memorize and transmit the input signals with a delay.

Another variation is the Hutton automaton , which allows for the replication of ring structures (see Langton's loops in English ).

• Von Neumann machine

• J. von Neumann, Theory of self-reproducing automata. M .: "World", 1971.