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

Chris Salzberg, Hiroki Sayama · 2025

Read Reflexive Composition of Elementary State Machines, with an Application to the Reversal of Cellular Automata Rule 90 by Chris Salzberg, Hiroki Sayama (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07186.txt.

Description

Chris Salzberg and Hiroki Sayama explore tiny state machines in a 2025 paper. A line of machines, each with two states and two symbols, updates in turn by a rule called reflexive composition. The full set holds two hundred fifty-six machines whose joint behavior was largely unmapped.

The space shows substitution patterns, reversible billiard-like motion, and fractal nesting. One machine draws the Sierpinski triangle and matches a famous cellular rule, Rule 90, under some edge settings. Two other machines trace Rule 90 in reverse, a first for this kind of system. Past methods hunted for prior states of the rule by search. The authors credit the equal treatment of state and message for the system's power.

Catalog record

CREATORChris Salzberg, Hiroki Sayama
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-07186

Browse the full library · About the Tower of Babel