Symbolic Dissection of Cellular Automaton Rule Number 110

Dimitry Gashinsky
RSA Security

A universal machine can simulate any effective process of symbol-manipulation, be it mathematical or anything else. It is a completely general instruction-obeying mechanism. In current practice, any actual computer approximates an ideal universal machine.

Cellular automaton (CA) rule 110 is a universal machine, so in theory it is capable of emulating any other machine.

I will be talking about my long term project to write a compiler for initial conditions of CA rule 110 from a higher level language. I think that it will have practical uses in the nanotechnology or in field-programmable gate array technology.

The first step of this project is to create a symbolic representation scheme for structures in rule 110. It will allow for easier experimentation with different initial conditions. The second step is to read back the output of the evolution of CA rule 110 and automatically produce symbolic representation of the structures. These two steps will allow me to catalog all of the interesting collisions between structures in CA rule110 in a symbolic form.

It is required to study the interactions between hundreds of structures in order to emulate complex computation in evolution of rule 110. The techniques that I discuss will allow me to do that without complex custom graphical tools.

Created by Mathematica  (April 20, 2004)