Measuring the Computational Power of Finite Patches of Cellular Automata

Attila Egri-Nagy, Chrystopher L. Nehaniv

Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation sem…