CALLIOPE · BCOM

Computation is just group theory in disguise: every program is a word in an algebraic structure acting on a state space, and making that structure a group (rather than a mere monoid) is exactly what reversibility means.

The core idea is simple. A computation takes a state, applies a sequence of operations, and produces a new state. That's a monoid action — a set of operations that can be composed and have an identity, but not necessarily undone. A standard Turing machine fits this picture exactly: each step rewrites the tape and moves the head, and because information gets overwritten, you can't generally run the machine backwards. The reachable states form an orbit under the transition map; everything else is unreachable by that program.

The interesting move is lifting this to a group action, where every operation has an inverse. Bennett (1973) showed how to do this constructively: augment the configuration space with a "history track" that records what was erased. The extended machine runs as a bijection — a reversible step — and projecting away the history track recovers the original irreversible computation. So irreversibility isn't fundamental; it's a consequence of forgetting. This connects directly to Landauer's principle: erasing information costs thermodynamic work, and reversible computation avoids that cost until the final readout.

On infinite symbolic tapes, reversible cellular automata (RCA) make this concrete and programmable. A cellular automaton is a rule that updates every cell simultaneously based on its neighborhood; it's reversible iff the rule is a bijection, and Hedlund (1969) showed that bijectivity is equivalent to the inverse also being a local rule. Partitioned/block constructions (Margolus 1984) give a clean recipe: alternate two phases of local permutations, and reversibility is guaranteed by construction. Crucially, one-dimensional RCA can already be universal — a single rule $F$ generates a cyclic group $\mathbb{Z}$ acting on the tape, and iterating $F$ simulates any Turing computation. Salo (2023) pushes further: the full automorphism group of the tape contains finitely generated universal subgroups, giving a fixed small "instruction set" whose words are programs.

The paper also covers two sharper results worth flagging. Barrington's theorem (1989) shows that width-5 permutation branching programs over a nonabelian group like $A_5$ capture exactly NC¹ — the complexity class of problems solvable by shallow parallel circuits. And a toy example grounds the abstraction: in the Rubik's Cube group, the commutator $[R^x, U^y]$ equals the identity unless $x=y=1$ , implementing a logical AND gate. The "program" is a group word; the "output" is whether the cube moved.

The upshot is a unified algebraic vocabulary for computation: monoids for irreversible dynamics, groups for reversible ones, with irreversibility recovered by coarse-grained observation. This frames the BCOM ontology's "transformations as primitives" perspective (Ruffini et al. 2025) in rigorous algebraic terms, and suggests that the right language for programmable physical systems — including neural or biological ones — may be the language of group actions.