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
| CREATOR | Chris Salzberg, Hiroki Sayama |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07186