What does it mean for a system to compute?

✨

This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Question: Is Everything a Computer?

Imagine you are watching a river flow. You see the water swirling around rocks, creating patterns. Now, imagine you are watching a human brain firing neurons. Finally, imagine you are watching a supercomputer crunching numbers.

To a physicist or a computer scientist, all three of these things are dynamic systems—things that change over time. But here is the big question the paper asks: Are they all "computing" something?

The Supercomputer: Yes, obviously. We built it to calculate math. We know exactly which wires represent numbers and which represent answers.
The Brain: We think it's computing thoughts, but we didn't build it. We don't have a manual that says, "This neuron means 'hello' and that one means 'goodbye'."
The River: Is it computing? Maybe it's calculating the path of least resistance? Or maybe it's just water?

The authors argue that while we can easily explain how a human-made computer works, it is incredibly difficult to figure out what a natural system (like a brain, a cell, or a storm) is actually "computing" because we didn't design the code.

The Two Types of "Computers"

The paper splits the world into two categories:

1. Constructed Computers (The LEGO Set)

These are things humans build, like your laptop or a calculator.

The Analogy: Imagine you build a house out of LEGO bricks. You decide that a red brick is a "wall" and a blue brick is a "window." You know exactly what every piece means because you put it there.
The Point: When we look at these, we have a "decoder ring" (a map) that translates the physical bricks into logical ideas. We know the input (you pressing a button) and the output (the screen showing a number).

2. Non-Constructed Computers (The Wild Forest)

These are things found in nature, like a flock of birds, a colony of ants, or a single cell in your body.

The Analogy: Imagine walking into a dense forest. You see trees, birds, and wind. You might say, "The birds are communicating!" or "The wind is shaping the trees!" But you didn't plant the trees or train the birds. You don't have a manual.
The Problem: If you look at a flock of birds, you could interpret their movement as a calculation of "how to avoid a hawk." But you could also interpret it as a calculation of "how to find the best seeds." Or maybe they aren't computing at all; maybe they are just reacting to the wind.
The Challenge: Since we didn't build them, we don't know which "decoder ring" to use. The same flock of birds could be running a million different "programs" depending on how you choose to look at them.

The Core Idea: The "Decoder Ring" (Mapping)

The authors propose a formal way to solve this. They say that for a system to be a computer, there must be a map (a translation guide) between the physical world and a logical computer.

The Physical World: The actual atoms, water, or neurons moving around.
The Logical Machine: The abstract idea of a computer (like a Turing Machine) that processes 1s and 0s.

The Rule: To say a natural system is computing, you must be able to draw a line from the physical state to a logical state without cheating.

No Cheating: You can't say, "The river is computing the answer to '2+2' because I decided that a splash of water means '4'." That's just making things up.
The Test: The map must be simple. If you have to do a super-complex calculation just to translate the river's water into a number, then the river isn't really computing that number; you are doing the work, not the river.

Why Does This Matter? (The "Value" of Computation)

The paper asks: If we can't always know what a natural system is computing, does it matter?

Yes, because of "Value."

The Analogy: Imagine a bird flying. It doesn't matter if the bird is "computing" aerodynamics or "computing" the location of a worm. What matters is that the bird survives.
The Insight: For living things, the "value" of the computation is how well it helps the organism survive. If a cell processes information to find food, that computation has high value. If it processes information and dies, the value is low.
The Future: The authors suggest that instead of trying to guess the exact "program" a brain is running, we should measure how much "computational power" it uses to stay alive.

The "Fluid Computer" and the Limits

The paper also discusses some wild examples, like fluids (water or air) potentially being computers.

The Idea: Some scientists have shown that if you swirl water in a specific tank, the patterns it makes could theoretically solve math problems.
The Catch: Even if the water can solve the problem, it's very hard to read the answer. The water doesn't stop and print "42" on a piece of paper. It just keeps swirling.
The Conclusion: Just because a system can theoretically do math doesn't mean it's a useful computer. A computer needs to be able to give you an answer you can actually use.

Summary: What's Next?

The paper concludes that we are still figuring out the rules for "natural computing."

We need better maps: We need a standard way to translate nature (brains, cells, weather) into computer language without making things up.
We need to measure "value": Instead of asking "What is this computing?", we should ask "How much does this computation help the system survive?"
We need to look at the whole picture: Real life isn't a one-time math problem (like 2+2). It's a continuous stream of inputs (like a conversation). Nature is a "continual computer" that is always open to the world, always changing, and never truly "finished."

In a nutshell:
We built our own computers and know exactly how they work. Nature built its own computers (us, animals, ecosystems), but we don't have the instruction manual. This paper is an attempt to write a new kind of manual that helps us understand what nature is "thinking" without assuming we know the answer before we start looking.

1. Problem Statement

The paper addresses a fundamental gap in the theory of computation regarding non-constructed computers (natural or artificial dynamic systems not explicitly designed to perform a specific computation, e.g., brains, cellular networks, turbulent flows, or insect colonies).

The Core Issue: For "constructed" computers (e.g., digital CPUs), the mapping between physical states and logical variables (input/output) is explicitly defined by the engineer. However, for non-constructed systems, there is no a priori decoding map.
The Ambiguity: A single dynamic system can be interpreted as performing an infinite number of different computations depending on how an observer chooses to map its physical degrees of freedom to logical variables.
The Question: Is there a principled, formal framework to identify which computation (or set of computations) a given dynamic system is emulating without relying on a pre-specified decoding map?

2. Methodology

The authors propose a rigorous mathematical framework based on emulation and coarse-graining to define the relationship between a physical dynamic system and an abstract computational machine.

A. Formal Definitions

Dynamic System: Defined as a triple $(X, T, f)$ , where $X$ is the state space, $T$ is time, and $f$ is the evolution operator satisfying deterministic, Markovian properties.
Computational Machine: An abstract dynamic system $(Y, T, g)$ evolving over logical variables.
Emulation: A physical system $(X, T, f)$ emulates a computational machine $(Y, T, g)$ if there exists a set-valued function $\phi$ (encoding) mapping elements of $Y$ to non-overlapping subsets (bins) of $X$ , such that the evolution of the physical system respects the evolution of the logical system:
$f(t, t', \phi(y)) \subseteq \phi(g(t, t', y))$
This implies that if the physical system starts in a state corresponding to logical state $y$ , its future states will remain within the bin corresponding to the next logical state $g(y)$ .
Decoding ( $\phi^{-1}$ ): The inverse map that translates physical states back to logical states.

B. Constraints on Decoding

To prevent trivial solutions (where the "computation" is hidden entirely within the encoding/decoding maps), the authors discuss imposing complexity constraints:

The encoding ( $\phi$ ) and decoding ( $\phi^{-1}$ ) functions should not be computationally more powerful than the system being emulated (e.g., they should be polynomial-time computable).
This ensures that the "work" of the computation is actually performed by the dynamics of the system, not by the observer's interpretation.

C. Analysis of Existing Literature

The paper surveys various domains to test this framework:

Neuroscience & Biology: Brains, insect colonies, and genetic regulatory networks.
Physics: Billiard ball models, chemical reaction networks (CRNs), and fluid dynamics (Euler/Navier-Stokes flows).
Abstract Systems: Cellular automata (CA) and symbolic dynamics.

3. Key Contributions

A. The Emulation Framework

The primary contribution is the formalization of emulation as a map between the evolution of a physical system and an abstract machine. This moves beyond the binary question of "Is this system Turing complete?" to the more nuanced question of "What specific machine is this system emulating, and under what decoding?"

B. Distinction Between "Fluid" and "Standard" Turing Completeness

The authors critically analyze recent claims that fluid flows (Euler equations) are "Turing complete."

Standard Emulation: Requires a map $\phi$ that tracks the system's state through every step of the computation (input $\to$ intermediate states $\to$ output).
Fluid Turing Completeness (FCTC): Recent literature defines a fluid system as Turing complete if it can determine whether a TM halts (a decision problem) by checking if a trajectory intersects a specific region.
Critique: The authors argue FCTC is insufficient for general computation because it does not provide the full trajectory of the computation (the intermediate states) and often requires an external "dovetailing" system to sift through infinite possibilities to find the output. It lacks the continuous, step-by-step emulation defined in their framework.

C. Quantifying "Value" vs. "Content" of Computation

The paper shifts focus from what is computed to the value of the computation.

Viability: In biological systems, the "value" of a computation is defined by how well it increases an agent's viability (e.g., fitness, free energy extraction).
Framework: They model an agent with memory ( $X_m$ ) and action ( $X_a$ ) interacting with an environment ( $Y$ ). The "computation" is the evolution of $X_m$ that optimizes the distribution of $X_a$ to maximize a viability function (e.g., minimizing KL divergence from a target distribution).

D. Future Directions for Quantification

The authors propose methods to quantify the amount of computation without identifying the specific algorithm:

Kolmogorov Rate: Estimating the fraction of a system's output string that is algorithmic (non-random) versus noise using the slope of Kolmogorov complexity ( $K(\omega) \approx \alpha n$ ).
Higher-Order Markov Chains: Measuring the "memory" or hidden states required to predict the system's future, serving as a proxy for computational depth.

4. Results and Findings

Universality of Interpretation: Without constraints, any dynamic system can be interpreted as performing any computation (including universal Turing machines) by choosing a sufficiently complex decoding map. This renders the question "What is this system computing?" ill-posed without additional constraints.
Limitations of Current Fluid Models: While fluid systems can simulate the halting condition of a TM, they do not currently satisfy the authors' stricter definition of emulation, which requires a coherent, step-by-step mapping of the entire computational trajectory.
Non-Constructed Computers are Ubiquitous: The framework applies to a vast array of systems, from single cells (genetic circuits) to societies, suggesting that "computation" is a fundamental property of dynamic systems, not just engineered devices.
Uncomputability: The paper acknowledges that some physical systems (e.g., certain quantum many-body systems) possess properties that are uncomputable by TMs, challenging the "Physical Church-Turing Thesis" in its strongest form.

5. Significance

Theoretical Unification: The paper provides a unified language to discuss computation across physics, biology, and computer science, bridging the gap between abstract logic and physical dynamics.
Redefining "Computer": It challenges the anthropocentric view that computers must be designed. It suggests that nature is inherently computational, and the role of the scientist is to find the "correct" (or most useful) decoding map that reveals the system's computational structure.
Practical Application: By focusing on the value of computation (viability) rather than just the logical output, the framework offers new tools for analyzing biological evolution, adaptive systems, and embodied AI.
Future Research Roadmap: The paper outlines critical open problems, including how to handle open, continual systems (like brains) that receive constant input, how to quantify collective computation in distributed systems, and how to rigorously define the "value" of computation in non-biological contexts.

In summary, Wolpert and Korbel argue that to understand computation in the real world, we must move beyond asking if a system is "Turing complete" and instead develop frameworks to identify the specific computational machines a system emulates, constrained by the physical limits of decoding and the functional value of the computation to the system's survival or operation.