JCA HomeIssue Contents

Quad Prize Submission:
Simulating Elementary CAs with Trid CAs
Edward Powley

The Trid neighbourhood is a three cell neighbourhood on a 2-dimensional lattice, and is a subset of the Quad neighbourhood. I show that, with an appropriately prepared initial configuration of “diagonal stripes”, a given elementary CA can be simulated by the two state Trid neighbourhood CA whose local update rule is precisely that of the elementary CA. Thus, invoking Cook’s universality result for elementary CA rule 110, I exhibit a universal two state Trid neighbourhood CA.

Keywords: Universal computation, Quad cellular automata, elementary cellular automata.

Full Text (IP)