One-rule cellular automata.

Von Neumann, Codd and others attempt to create universal computing machines using neighborhood transformations in a cellular space. Although the proposed machines are theoretically possible, they are too complex to be constructed. Here, a simple universal computer is presented that uses a single transformation. The transformation is applied to the array by first searching for a pattern of spatially cells in parallel and then replacing it with another pattern. Configurations of cells are arranged to realize dual-rail logic operators and connection primitives. It is shown that these logic and connection configurations are sufficient to construct a Turing machine. The present techniques provide a new perspective from which to view computational complexity as well as provide a foundation for work on optical digital computers.