Complex Systems

Logical Universality from a Minimal Two-Dimensional Glider Gun Download PDF

José Manuel Gómez Soto
Department of Mathematics
Autonomous University of Zacatecas
Zacatecas, Zac. Mexico
jmgomez@uaz.edu.mx
https://matematicas.reduaz.mx/~jmgomez

Andrew Wuensche
Discrete Dynamics Lab
andy@ddlab.org
https://www.ddlab.org

Abstract

To understand the underlying principles of self-organization and computation in cellular automata, it would be helpful to find the simplest form of the essential ingredients, glider guns and eaters, because then the dynamics would be easier to interpret. Such minimal components emerge spontaneously in the newly discovered Sayab rule, a binary two-dimensional cellular automaton with a Moore neighborhood and isotropic dynamics. The Sayab rule's glider gun, which has just four live cells at its minimal phases, can implement complex dynamical interactions and the gates required for logical universality.

Keywords: universality; cellular automata; glider gun; logical gates