Arithmetical Cellular Automata

Johan Veerman

Pontificia Universidad Católica

Cellular automata (CA) are a class of local parallel discrete systems that, in some cases, have universal computation capabilities. Therefore, it would seem that in order to perform a particular type of computation, this would only be a matter of adequately encoding the input as an initial condition and decoding the output, and then search exhaustively for CA in a rule space with enough colors or states to contain the coding scheme. Unfortunately, there are two problems with this approach. The first one is that we do not know how to encode an initial condition in order to make a universal CA compute some mathematical function. We therefore have to build our own scheme with more states. This leads us to the second problem. As more colors are used for higher mathematical functions, it becomes unfeasible to search exhaustively in the corresponding rule space.

Using a bottom-up approach, we start specifically constructing CA to calculate some elementary arithmetical functions both in a serial and in a parallel way. We then use these results for narrowing down the rule space to perform a more directed search. Some considerations are given regarding this search method and the distribution of the arithmetical CA in the rule space. Furthermore, since CA are good candidates for parallel computation, studying the way in which CA can compute mathematical calculations can lead the way to new computing architectures as well as to an understanding of the connections between natural and computational systems.

[presentation materials]