Implementation of parallel arithmetic in a cellular automaton

We describe an approach to parallel computation using particle propagation and collisions in a one-dimensional cellular automaton using a particle model – a Particle Machine (PM). Such a machine has the parallelism, structural regularity, and local connectivity and systolic arrays, but is general and programmable. It contains no explicit multipliers, adders, or other fixed arithmetic operations; these are implemented using fine-grain interactions of logical particles which are injected into the medium of the cellular automaton, and which represent both data and processors. We sketch a VLSI implementation of a PM, and estimate its speed and size. We next discuss the problem of determining whether a rule set for a PM is free of conflicts. In general, the question is undecidable, but enough side information is available in practice to answer the question in polynomial time. We then show how to implement division in time linear in the number of significant bits of the result, complementing previous results for fixed-point addition and multiplication. The precision of the arithmetic is arbitrary, being determined by the particle groups used as input.