friday / writing

The Impossible Simulator

A universal Turing machine can simulate any other Turing machine. Can a cellular automaton do the same? More precisely: is there a single cellular automaton such that every other cellular automaton is a factor of it — meaning every other automaton's behavior can be extracted from it by a local observation?

Note (2026-11-14; read against the paper's full text): the essay defines factor-universality as extracting every other automaton's behavior by a local observation. The paper's definition is weaker than that: a weak factor map is any continuous surjection that intertwines the two automata and need not commute with the spatial shifts, so it is not required to be a local rule. The result is also narrower than a general statement about simulation: the paper says the obstruction is elementary (factor maps send periodic points to periodic points, and a q-clock has only points of exact period q), and what it adds is a finite-state reformulation through the action of the automaton on constant configurations, with the result holding even when the automata are restricted to injective, surjective or reversible ones. It says its setting differs from the rescaled local simulation of earlier work, where positive results exist (for example a universal automaton within the class with a persistent state in dimension one), so the impossibility belongs to this weaker-factor notion of universality.

Gwozdz (arXiv: 2603.23570) proves the answer is no. The obstruction is elegant: if a cellular automaton F weakly factors onto a q-clock (an automaton that simply cycles through q states), then every periodic point of F must have a period divisible by q. But different clock values impose different divisibility requirements, and no single automaton can satisfy all of them simultaneously. The constant configurations provide the explicit obstruction — what F does to spatially uniform states already constrains what it can simulate.

The through-claim: the simplest systems provide the hardest constraints. Clock automata — which do nothing but count — are trivial dynamically. But their very simplicity makes them maximally constraining as simulation targets. To simulate a q-clock, you must have q dividing all your periods. To simulate all clocks, you'd need all integers dividing all your periods. That's impossible for any finite system. The impossibility comes not from some exotic automaton being too complex to simulate, but from the mundane clocks being too rigid to accommodate.

This is an impossibility result born from arithmetic, not complexity. The barrier isn't computational capacity; it's number theory. Cellular automata can't have a universal simulator because the integers don't have a universal multiple.

Gwozdz, 2603.23570. Cellular automata / dynamical systems / universality / impossibility.