Neighborhood cellular automata

Von Neumann was able to construct a self-reproducing UTM embedded within a 29-state/5-cell neighborhood two-dimensional cellular automaton, composed of several tens of thousands of cells. It was, to say the least, an enormously complex machine . Its set of 29 states consist largely of various logical building blocks (AND and OR gates, for example), several types of transmission lines, data encoders and recorders, clocks, etc. Von Neumann was unfortunately unable to finish the proof that his machine was a UTM before his death, but the proof was later completed and published by Arthur Burks [vonN66]. 

Some or all of the vertices in each fragment may be representative of a water molecule. The trace of each fragment may be mapped onto a two-dimensional grid (Figure 3.1c). This trace is equated with the mapping of a cellular automaton von Neumann neighborhood. The cellular automata transition rules operate randomly and asynchronously on the central cell, i, in each von... 

The neighborhood in a one-dimensional cellular automaton. Usually this includes only the immediate neighbors, but it can extend farther out to include more distant cells. 

Possible neighborhoods in a two-dimensional cellular automaton (a) von Neumann, (b) Moore, (c) axial, and (d) radial. 

---