Reflexive Composition of Elementary State Machines, with an Application to the Reversal of Cellular Automata Rule 90

We explore the dynamics of a one-dimensional lattice of state machines on two states and two symbols sequentially updated via a process of"reflexive composition."The space of 256 machines exhibits a variety of behavior, including substitution, reversible"billiard ball"dynamics, and fractal nesting. We show that one machine generates the Sierpinski Triangle and, for a subset of boundary conditions, is isomorphic to cellular automata Rule 90 in Wolfram's naming scheme. More surprisingly, two other machines follow trajectories that map to Rule 90 in reverse. Whereas previous techniques have been developed to uncover preimages of Rule 90, this is the first study to produce such inverse dynamics naturally from the formalism itself. We argue that the system's symmetric treatment of state and message underlies its expressive power.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-05-12

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2505.07186arXiv 2505.07186
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Self-Reproduction and Evolution in Cellular Automata: 25 Years after Evoloops

  2024cited by this paper
• Counting Preimages of Homogeneous Configurations in 1-Dimensional Cellular Automata

  2010cited by this paper
• Algorithms for computing preimages of cellular automata configurations

  2007cited by this paper
• A graph-based reflexive artificial chemistry

  2007cited by this paper
• From Machine and Tape to Structure and Function: Formulation of a Reflexively Computing System

  2006cited by this paper
• A New Kind of Science

  2003cited by this paper
• “The arrival of the fittest”: Toward a theory of biological organization

  1994cited by this paper
• Predecessors of cellular automata states: I. Additive automata

  1993cited by this paper
• Invertible cellular automata: a review

  1991cited by this paper
• Genetic information and the determination of functional organization in biological systems

  1989cited by this paper
• Enumeration of Preimages in Cellular Automata

  1989cited by this paper
• Algebraic properties of cellular automata

  1984cited by this paper
• Computation: Finite and Infinite Machines

  1967cited by this paper
• On Computable Numbers, with an Application to the Entscheidungsproblem.

  1937cited by this paper
• An Unsolvable Problem of Elementary Number Theory

  1936cited by this paper

• No citing papers are available for this paper.