Complex Systems

Universal Computation in Few-body Automata Download PDF

Michael Biafore
Department of Physics,
Massachusetts Institute of Technology,
Cambridge, MA 02139, USA


Few-body automata are a class of cellular automata. They were developed specifically to investigate the possibility of implementing a new generation of cellular automata machines that would use dense arrays of nanometer-scale device-cells. In this paper, we try to determine how many states per cell are required by few-body automata in order to perform universal computation. We prove theorems describing the space, time, and state-set complexity of the simulation of -dimensional conventional cellular automata with -body automata, and show that there exist computation-universal 2-body automata requiring 5.81 bits of state per cell for and 2 bits per cell for . These results suggest that physically-imposed restrictions on the number of available bits per cell will not be an obstacle to cellular automaton-like computation at nanometer scales.