CALLIOPE · BCOM

Here we address the mathematical definition of algorithmic agents grounded on the theory of computation (three-tape Turing machine pairs) and algorithmic information theory (AIT). We show that there is a sense in which an agent may be identified from its behavior and in which agent modules such as the objective function or modeling engine exist, even if it may be generally hard to identify them in practice. We next analyze the problem raised by computational and algorithmic degeneracy for the thesis that algorithmic structure is related to measurable outputs of agents such as first-person reports or physiological measurements. We argue that although there are multiple ways to set up a computational system to implement an algorithm, high-level algorithmic structure (the program) and the coarse-grained core of computational dynamics must share some features, which are also present in the Kolmogorov optimal program. This means that what a system does (its input-output relation) cannot be fully disentangled from how it does it (computational functionalism) or what it is (since computation is physical).

A rigorous mathematical definition of what it means to be an agent — and why you can't fully separate what a system does from how it does it.

The core problem this paper attacks is deceptively simple: what exactly is an agent, in a mathematically precise sense? Not hand-wavy ("something that perceives and acts"), but a definition tight enough to (a) rule out trivial systems, (b) let you check whether a black-box system qualifies, and (c) say something meaningful about the internal structure of agents you can't directly inspect. The author's broader project — the Kolmogorov Theory of structured experience — needs this foundation because it claims that the algorithmic structure of what a brain runs is related to the structure of conscious experience. That claim is meaningless without a precise notion of agent and algorithmic equivalence.

The definition built here uses a Turing-pair setup: two three-tape Turing machines, one playing Agent and one playing World, with their input/output tapes cross-connected. An agent must satisfy three conditions simultaneously: it must run a compressive and informative world model (the model both shortens the history of percepts and retains genuine predictive power about future percepts, measured via Kolmogorov mutual information); it must have a non-trivial scalar objective function that actually varies across model states; and it must plan by selecting actions that maximize expected future objective value. A thermostat passes — the paper proves this formally. A machine that just prints "1" regardless of input fails on conditions two and three, which is the point: the definition has teeth.

The paper then develops three notions of equivalence between agents. Functional equivalence ignores internal state entirely and only matches input-output behavior. Rigorous equivalence also demands that internal tape contents can be mapped across systems. Kolmogorov equivalence — the most interesting — says two agents are equivalent if their shortest possible programs (their Kolmogorov-optimal descriptions) are the same. This last notion collapses the "degeneracy" problem: many different programs can produce the same outputs, but they all share a common compressed core. The paper argues that this shared core is what matters — causally disconnected computations (code that runs but never affects any output) can always be factored out, and what remains is the essential algorithmic structure.

This leads to the paper's sharpest philosophical point, which it calls a refutation of the "unfolding/substitution argument." That argument says: since you can implement the same input-output function in arbitrarily many ways, theories that tie conscious experience to computational structure are hopeless. The paper's counter is that this objection only holds if you restrict "outputs" narrowly. Once you expand outputs to include all measurable physical quantities — neural firing patterns, transistor currents, anything — the degeneracy collapses. Computation is physical, so what a system does (its full measurable behavior) cannot be disentangled from how it does it. The paper formalizes this via "algorithmic coarse-graining": even if two implementations differ at the bit level, their high-level algorithmic structure — the part that actually drives outputs — must share features, and those shared features are precisely what appears in the Kolmogorov-optimal program.

The source is a full technical paper with formal definitions, proofs, pseudocode, and Python implementations. It is dense but self-contained. The thermostat example runs throughout as a concrete anchor, and the appendix includes working simulation code that instantiates the formal agent definition explicitly.