Universal Computation in Few-body Automata
Michael Biafore
Department of Physics,
Massachusetts Institute of Technology,
Cambridge, MA 02139, USA
Abstract
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.
