Dynamics as Computation and Nontrivial Implementation

A clean criterion for when a physical system genuinely computes something, rather than just being relabeled to look like it does.

The core puzzle is this: computation is just state-transition dynamics — a machine moves from state to state according to a rule, and so does any physical system. So in what sense is a silicon chip "really" computing while a rock is not? The obvious answer is that you can find a mapping from the rock's physical states to the states of any finite machine you like, and the dynamics will trivially match. Putnam made this precise: given enough physical microstates and unconstrained freedom to define what counts as "state A" vs. "state B," almost any open system implements almost any finite-state machine. That's the triviality problem.

The paper draws a sharp line between two things that often get conflated under "pancomputationalism." The weak reading — that physical law is mathematical, so the universe "computes" its next state — is basically harmless. The strong reading — that therefore any physical system implements any computation — is the one that collapses all meaningful distinctions. The Putnam construction works by defining machine states as disjunctive unions of time-slices from one observed trajectory. It's a lookup table built after the fact. The mapping carries the computation, not the physics.

To block this without abandoning the "dynamics = computation" intuition, the paper proposes two conditions on the coarse-graining map (the function that reads machine states off physical states). First, the map must have low Kolmogorov complexity — it must be compressible, like "voltage above threshold = 1," not a bespoke enumeration of which specific microstates count as which machine state. Second, the map must be trajectory-independent: it cannot carry significant algorithmic information about the particular physical run it's supposed to explain. These two conditions are formalized as a $(k, c)$-implementation criterion, where $k$ bounds the description length of the mapping and $c$ bounds how much the mapping "knows" about the realized trajectory.

The result is a principled, information-theoretic filter. A rock doesn't implement a Turing machine not because the semiconjugacy equation fails, but because any mapping that makes it work would need to encode the rock's specific history — violating trajectory-independence — or be astronomically complex — violating the low-$K$ condition. Meanwhile, a transistor circuit passes: the mapping ("high voltage = 1") is short to describe and doesn't depend on which particular computation was run. The paper also notes, carefully, that even the Putnam result only covers finite-state machines; programmable universality requires systematic input encoding and correct counterfactual behavior, which no ex-post labeling trick provides.