My goal is to create an open-source package in Python that allows people to build custom cellular automata and study the mathematical theorems governing them. Some questions of interest are:

  • How important is the lattice geometry?
    • Can every two-dimensional automaton be described by an one-dimensional automaton?
    • Does a cellular automaton on a triangular lattice have the same behavior as one on a square lattice?
    • How similar is a cellular automaton on a lattice whose sites are randomly distributed to one whose sites are uniformly distributed?
  • What is the behavior of a cellular automaton which has an evolving governing function?
  • Probabilistic cellular automata.
    • How much do they differ from their deterministic counterparts?
  • Can a cellular automaton return to its initial state after a finite time?
  • Do all cellular automata map their initial states to the entire set of states? This questions tries to study if cellular automata are bijective functions. If not, how big is the subset of those that are bijective?
  • How important are the boundary conditions?

Most of these questions have already been answered. I will try to track the corresponding references and add them to the resources list below.

Resources:

  • Github repository: https://github.com/stratisg/Cellular-automata
  • Wikipedia article on cellular automata: https://en.wikipedia.org/wiki/Cellular_automaton
  • Wikipedia article on self-replication: https://en.wikipedia.org/wiki/Self-replication
  • Wikipedia article on coupled map lattice: https://en.wikipedia.org/wiki/Coupled_map_lattice
  • Wikipedia article on probabilistic/stochastic cellular automata: https://en.wikipedia.org/wiki/Stochastic_cellular_automaton
  • Wikipedia article on Von Neumann universal constructor: https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor
  • Wikipedia article on Greenberg–Hastings cellular automaton: https://en.wikipedia.org/wiki/Greenberg%E2%80%93Hastings_cellular_automaton
  • Wikipedia on Garden of Eden (cellular automaton): https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton)
  • Wikipedia on digital physics: https://en.wikipedia.org/wiki/Digital_physics
An example of an one dimensional cellular automaton. The x-axis shows the each site’s value, either a zero (white) or one (black), at a given time. The y-axis stands for the time with earlier times being at the top and later times at the bottom.