When Does a Physical System Compute?
Companion post to:
A category-theoretic perspective on physical computation, biological computation, and system compositionality
Nima Dehghani, Gianluca Caterina
Journal of Physics: Complexity . Volume 5, Number 3
DOI: https://doi.org/10.1088/2632-072X/ad6051
When Does a Physical System Compute?
In classical computer science, the direction of thought is usually clear. We begin with an abstract notion of a computable function. We then define a model of computation, such as a Turing machine, lambda calculus, finite-state automata, process calculi, or other formally equivalent models. Finally, we build physical devices that implement those models. In that direction, the conceptual pipeline is relatively well behaved:
\[\text{computable function} \rightarrow \text{model of computation} \rightarrow \text{physical device}.\]This is the direction that gave us digital computers, programming languages, and much of modern computational theory.
But many of the most interesting questions in physical, biological, and unconventional computation go in the opposite direction. We are not always handed a clean abstract function and then asked to build a machine that computes it. Instead, we often begin with a physical system: a quantum device, a neural circuit, a biochemical signaling pathway, a cellular regulatory network, a bacterial colony, or a brain. We observe that the system has states, transitions, dynamics, information flow, constraints, and perhaps adaptive behavior. Then we ask:
Is this system computing?
That reverse direction is much harder:
\[\text{natural system} \rightarrow \text{physical operations} \rightarrow \text{mathematical abstraction}.\]The difficulty is that natural systems change state all the time. Electrons move. Molecules interact. Cells signal. Brains evolve through high-dimensional neural trajectories. A rock rolling down a hill follows physical law. The Solar System evolves according to gravitational dynamics. But we do not want a definition of computation so weak that every physical state transition becomes a computation. If everything computes simply because it changes state, then computation has lost its explanatory power.
This is the central motivation of our paper:
Physical computing: a category theoretic perspective on physical computation and system compositionality
Nima Dehghani and Gianluca Caterina
Journal of Physics: Complexity 5, 035005, 2024
DOI: 10.1088/2632-072X/ad6051
The paper develops a category-theoretic framework for physical computation. The goal is not to add another metaphor to the already crowded discussion of whether brains, bacteria, slime moulds, chemical waves, or quantum systems “compute.” The goal is to provide a formal way to ask when a physical process can be treated as a computation, under what constraints, and at what scale.
The problem with saying that everything computes
The history of physical computation is entangled with a persistent problem: pancomputationalism. In its broadest form, pancomputationalism is the view that every physical system computes, or at least that every physical system implements some computation. The reasoning often begins with the observation that physical systems have states and transitions. If we can map those physical states onto computational states, then perhaps the system implements the corresponding computation.
This idea appears in different forms in debates about concrete computation. Hilary Putnam’s “simple mapping account,” for example, showed how dangerously permissive such mappings can become. If all that is required is a mapping between the states of a physical system and the states of an abstract automaton, then almost any sufficiently rich physical system can be interpreted as implementing almost any finite-state computation. A rock, under the right mapping, could be said to implement a finite-state automaton. A physical object moving through space could be said to compute its own trajectory. The Solar System could be said to compute the laws of motion.
This is not a useful theory of computation. It may reveal something important about the danger of arbitrary mappings, but it does not tell us what distinguishes a physical computer from a physical system merely undergoing change.
The issue becomes especially serious in biological and neural systems. In biology, it is tempting to describe almost every regulatory process as computation. Cells process signals. Bacteria integrate environmental cues. Neural circuits transform sensory inputs into motor outputs. Organisms maintain internal variables, regulate themselves, and respond to perturbations. But if “computation” simply means “information processing,” and if “information processing” simply means “a physical system changes in response to another physical system,” then the concept becomes too broad.
A useful account of biological computation needs to be stricter. It must be able to say that some physical processes support computation, while others may involve signaling, regulation, causal coupling, or information transfer without thereby becoming computations in the relevant sense.
From abstraction/representation theory to categorical structure
A major starting point for our work is the Abstraction/Representation framework developed by Horsman, Stepney, Wagner, and Kendon. Their framework was motivated partly by quantum computation and unconventional computation. It asks: when does a physical system compute?
Their answer is built around a “compute cycle.” A physical system evolves according to physical dynamics. At the same time, an abstract representation of that physical system evolves according to an abstract computational rule. A physical system computes when the physical evolution and the abstract evolution correspond in the right way. This correspondence can be drawn as a commuting diagram: one path evolves the physical system and then abstracts it; the other path abstracts it first and then evolves the abstraction. If the diagram commutes, the physical evolution can be used to predict the abstract evolution.
This was an important conceptual step because it made explicit that physical computation involves a relationship between physical dynamics and abstract representation. A physical computer is not just a lump of matter. It is a system whose physical evolution is usable as the evolution of an abstract computation.
However, the abstraction/representation framework also leaves open a difficult question: what constrains the mapping between the physical and abstract domains?
If the mapping is too loose, then the framework risks inheriting the same problem as simple mapping accounts. A mapping alone is not enough. We need a way to specify when a mapping preserves the relevant structure of the physical process and the abstract process. We need to know how computations compose, how representations relate to one another, how different physical systems can realize the same computation, and how nested systems can support computation across scales.
This is where category theory becomes useful.
Why category theory?
Category theory is often described as the mathematics of structure and compositionality. That description is accurate, but it can sound too general. In this context, the usefulness of category theory is quite concrete.
Computation is not just about isolated states. It is about transformations between states, and transformations that can be composed. A program takes an input and produces an output. A physical process takes a physical system from one state to another. A computation may be refined, decomposed, implemented at different levels, or realized in multiple substrates. These are all relational and compositional notions.
Category theory gives us a language for this.
A category consists of objects and morphisms. Morphisms are arrows between objects. They can be composed. Each object has an identity morphism. These simple ingredients are powerful because they allow us to describe systems in terms of their structure-preserving transformations.
In our framework, we define a category of physical processes and a category of abstract processes.
The physical category, which we call PhysProc, has physical systems as objects. Its morphisms are physical processes that transform one physical system or state into another. These processes take finite time and can be composed sequentially.
The abstract category, which we call AbsProc, or more concretely Comp in the paper, contains abstract computational objects. In a pragmatic version, the objects may be data types such as Booleans, integers, reals, or other formal objects. The morphisms are programs or abstract operations that transform inputs into outputs.
The key move is this:
A physical computation is not an arbitrary mapping between physical states and abstract states. It is a structured functorial relationship between a category of physical processes and a category of abstract processes.
A functor maps objects to objects and morphisms to morphisms while preserving composition and identity. This is crucial. It means that the physical-to-abstract relationship must preserve the structure of processes, not merely assign labels to states.
If a physical process takes (p_1) to (p_2), and if those physical states are represented abstractly as (c_1) and (c_2), then the abstract transition from (c_1) to (c_2) must correspond to the physical transition. The mapping has to respect the dynamics. It must preserve the process structure.
This is what prevents arbitrary reinterpretation. A functorial account asks not only whether we can associate physical states with computational states, but whether the transitions, compositions, and process structure are preserved.
Physical computation as a pair of functors
In the paper, we formulate physical computation using functors between physical and abstract process categories. Schematically, one functor maps physical processes into abstract processes:
\[\mathcal{R}_T : \textbf{PhysProc} \rightarrow \textbf{AbsProc}.\]This is the abstraction or representation direction. It tells us how a physical system, under a theory (T), is represented as an abstract computational process.
But physical computation also requires a way of relating abstract processes back to physical processes. In the strict version, this can be understood through an inverse-like relationship, where the abstract process and physical process are aligned strongly enough that the physical system can serve as a computer for that abstraction.
In a more flexible version, this relationship can be relaxed using adjunctions. This matters because physical computation often does not involve exact identity between levels. Different physical devices can implement the same abstract computation. A silicon circuit, a quantum device, a mechanical billiard-ball computer, and perhaps a biological circuit can all instantiate related computational structures without having identical physical states.
Thus, the categorical view allows us to distinguish between several levels of physical-computational relationship. Some systems may support a strict equivalence between physical and abstract process structure. Others may support a looser but still structured relationship through adjoint functors. What matters is that the relationship is not arbitrary. It is constrained by the morphisms of the physical system and the morphisms of the abstract process.
This also gives us a way to talk about the “amount” or “type” of computation a physical system can support. The computational capacity of a physical system is related to the image of the abstraction functor. A system with rich controllable dynamics, stable distinguishable states, and composable operations can support a richer abstract process structure. A system without such structure may undergo physical evolution without being a computer in the relevant sense.
Computation is not just representation
One important implication of the framework is that computation should not be reduced to representation alone. A representation is not enough. The relation between physical and abstract systems has to preserve the right structure.
This is where the categorical approach differs from weak mapping accounts. In weak mapping accounts, one can often invent a mapping after the fact. The mapping may associate physical states with computational states, but it does not necessarily preserve the causal and counterfactual structure of the physical system. It does not necessarily respect what the system could have done under different inputs, boundary conditions, or perturbations.
In the functorial framework, the morphisms matter. The physical transitions themselves are part of the structure being mapped. This means that causal and counterfactual constraints are not external decorations added later to rescue the theory. They are naturally tied to the preservation of process structure.
If a physical system can move from (p_1) to (p_2), and this transition corresponds to an abstract transition from (c_1) to (c_2), then the computation depends on that physical transition being permissible under the system’s dynamics. Likewise, if alternative physical transitions are possible under alternative conditions, the abstract process must respect those alternatives if it is to capture the computation performed by the system.
This matters for physical computing generally, and it matters especially for biological systems. A biological process may be meaningful, regulated, adaptive, and causally rich without necessarily constituting a computation under a given abstraction. The question is not whether we can describe it computationally after the fact. The question is whether the process structure of the biological system maps functorially onto an abstract computational process.
Natural transformations: refinement and change of representation
Once computation is understood functorially, we can ask a second-order question: how do different representations of the same physical computation relate to each other?
This is where natural transformations enter.
A natural transformation is a morphism between functors. If functors are structure-preserving maps between categories, then natural transformations are structure-preserving maps between such maps. They are sometimes described as “relations between relations,” which is exactly what we need when thinking about computational refinement.
Consider a simple example: addition. A physical device may implement addition at the binary level. But a user may think in decimal. Another representation may use octal. These are different abstract representations of related computational structure. The device’s physical dynamics may be binary, while the intended high-level operation is decimal addition. The relationship between these abstraction levels can be described using natural transformations.
This gives a formal account of computational refinement. A computation can be represented at one level, then refined into another representation, and the relationship between those levels can be expressed categorically. This is not merely a software engineering convenience. It is a way of describing how physical processes, low-level operations, and high-level computations remain coherently related.
For biological and neural systems, this is particularly important. A neural circuit can be described at many levels: ion channels, synapses, dendritic compartments, spiking dynamics, population trajectories, behavior, and perhaps cognitive variables. These levels are not interchangeable. But they may be related by structured transformations. A categorical framework gives us a way to ask when such cross-level descriptions preserve computational structure and when they are merely descriptive projections.
Multiple realizability and adjunctions
A central idea in philosophy of mind, computational neuroscience, and cognitive science is multiple realizability. The same abstract function can be implemented in different physical substrates. A computation may be realized in silicon, in a mechanical device, in a quantum system, or perhaps in a biological system.
David Marr’s tri-level framework made this idea familiar in neuroscience: one can distinguish the computational level, the algorithmic or representational level, and the implementational level. But the mathematical relationship between these levels is often left informal. We say that the same computation can be implemented in different ways, but what exactly does that mean?
In our framework, adjoint pairs provide a way to formalize this idea. Rather than requiring a strict identity between abstract and physical process categories, we can allow a structured relationship in which mappings back and forth preserve the relevant computational organization in a weaker, but still disciplined, way.
This is important because different physical systems rarely share identical state spaces. A transistor circuit, a quantum dot system, and a neural circuit do not have the same physical degrees of freedom. Yet they may support related abstract processes. Adjunctions allow us to describe this without collapsing all physical details into a vague claim of “implementation.”
This also clarifies what medium independence can and cannot mean. Computation is often said to be medium-independent, but this phrase is easy to misuse. It does not mean that the physical medium is irrelevant. It means that the same abstract computational structure may be realizable in different media, provided that each medium has the appropriate physical degrees of freedom, controllable operations, and read/write structure to support the relevant abstract process.
The medium matters because it determines which physical morphisms are available. It determines what can be written, transformed, stabilized, coupled, measured, and read out. The abstract computation may be multiply realizable, but each realization is constrained by physical dynamics.
Scale matters
The categorical framework also makes clear that physical computation is scale-dependent.
Consider quantum computation. An isolated electron spin is not, by itself, a computer. It has physical degrees of freedom, but computation requires more than the existence of distinguishable physical states. The spin must be embedded within a larger architecture that allows preparation, controlled evolution, coupling, measurement, and interpretation. In a spin qubit system, the relevant physical degrees of freedom become computational only within a write-control-read structure that supports abstract operations.
The same point applies to quantum-dot cellular automata. Individual quantum dots have physical properties. But the computational system emerges from the designed arrangement, interactions, boundary conditions, and input/output structure. The computation is not simply “inside” the quantum dot as a metaphysical property. It is supported by a structured physical process that maps onto an abstract process.
This is also true in biology. A molecule binding to another molecule is a physical event. A signaling pathway propagating a state change is a physical and biochemical process. A gene regulatory network stabilizing a cell fate is a dynamical system. Whether any of these are computations depends on the scale of description, the available morphisms, the compositional structure, and the abstraction under which the physical process maps to an abstract process.
This is why the question “does the brain compute?” is too coarse. A better question is:
Which physical processes in the brain, at which scales, under which abstractions, and with which compositional structure, constitute computations?
This reframing avoids both extremes. It avoids the simplistic claim that the brain is “just a computer.” It also avoids the equally unhelpful claim that biological systems are too embodied, continuous, or material to be understood computationally. The categorical view allows us to examine specific candidate computations in neural and biological systems with formal precision.
Nested composition and biological systems
Biological systems are not flat. They are nested, modular, and multiscale. Molecular interactions compose into pathways. Pathways compose into regulatory networks. Cells compose into tissues. Neural circuits compose into larger circuits and brain-wide dynamics. Organisms interact with environments. Each level has its own variables, constraints, and characteristic timescales.
The paper introduces nested composition as a way to think about such systems. The idea is that an abstraction of one physical process can itself become part of another physical process. A physical system (P) may have state transitions that map to an abstract process. That abstracted process may then be coupled to another physical system (P’), whose own state transitions are mapped into another abstraction, and so on.
This is not just hierarchy in the ordinary sense. It is compositional nesting across physical and abstract domains. The abstraction of one physical process can feed into the dynamics of another. Linked open dynamical systems with shared variables can therefore be understood as nested compositional structures.
This is highly relevant to systems biology. Biological computation, if it exists in a given case, is unlikely to be localized to a single molecular event. It is more likely to arise from structured interactions among components, constraints, feedback loops, and readout mechanisms across scales. Category theory gives us a formal language for asking how these components compose.
It also helps distinguish computation from information transfer. Biological systems constantly transfer information in a broad physical sense. But not every transfer of information is computation. For a biological process to count as computation under this framework, the relevant physical transitions must map coherently into an abstract process category. The system must support more than correlation, signaling, or causal influence. It must support structured, composable operations.
Implications for computational neuroscience
Computational neuroscience often uses computational language at multiple levels. We speak of neurons encoding variables, circuits implementing algorithms, cortical areas performing inference, populations representing latent states, synapses storing information, and brains computing predictions. Some of this language is productive. Some of it is metaphorical. Some of it may be misleading.
The framework in this paper is not meant to abolish computational language in neuroscience. Rather, it gives us a way to make that language more precise.
For a neural system, we can ask:
What are the relevant physical objects?
Are they ion channels, neurons, synapses, local field potentials, cell assemblies, population trajectories, or brain regions?
What are the morphisms?
Are they spike transitions, synaptic updates, dynamical flows, network state transitions, behavioral transformations, or experimentally controlled input-output relations?
What is the abstraction functor?
How are physical states mapped into abstract states? What structure does that mapping preserve?
What counts as composition?
Can the relevant operations be composed in a way that supports an abstract computational process?
What are the causal and counterfactual constraints?
Would the system support the same abstract transition under relevant perturbations, inputs, or boundary conditions?
These questions push us beyond loose statements such as “the cortex computes prediction error” or “the brain performs Bayesian inference.” Such statements may be useful hypotheses, but the categorical view asks what physical process category is being mapped into what abstract process category, and whether the mapping preserves the relevant dynamics.
This is especially important in modern neuroscience, where high-dimensional neural data can often be described by many different abstract models. The same neural population activity might be interpreted as encoding, decoding, inference, control, attractor dynamics, dynamical systems evolution, or manifold traversal. A categorical framework asks how these descriptions relate. Are they refinements of one another? Are they different abstraction functors? Are there natural transformations between them? Do they preserve the same process structure, or are they merely alternative descriptions imposed after the fact?
That is a much sharper way to discuss computation in the brain.
Implications for unconventional and quantum computing
The same framework also applies to unconventional computing and quantum computing.
In unconventional computing, one often uses physical processes directly: chemical waves, slime mould growth, DNA interactions, mechanical collisions, memristive materials, neuromorphic substrates, or quantum systems. These systems are interesting precisely because they do not always resemble classical digital computers. They may be continuous, stochastic, embodied, spatially extended, or strongly substrate-dependent.
The categorical approach does not require them to look like classical computers. It does not demand that every physical computer be a digital machine. Instead, it asks whether the physical process structure can be mapped into an abstract process category in a way that preserves the relevant operations.
This is a useful standard. It allows us to take unconventional computing seriously without turning every interesting physical process into a computer. It also makes clear that the physical substrate is not merely an implementation detail. In quantum computation, for example, the available operations depend on the structure of the physical system: superposition, entanglement, unitary evolution, measurement, decoherence, and control constraints. The abstract computational power of the system is inseparable from the physical morphisms it supports.
Thus, the framework is broad enough to include quantum and unconventional systems, but strict enough to avoid the claim that all physical systems compute merely by evolving.
What the framework rules out
One of the strengths of a good scientific framework is not only what it explains, but what it refuses to explain too easily. A theory that can be modified to fit any observation is weak. A useful theory should be hard to vary. It should prevent certain bad explanations.
The categorical framework rules out the idea that arbitrary mapping is sufficient for computation. It rules out the idea that any physical state transition is automatically computational. It rules out the idea that information transfer and computation are identical. It rules out the idea that medium independence means substrate irrelevance.
It also rules out a common confusion in modeling. A model of a physical system may compute predictions about that system. But the physical system itself is not thereby computing the model. A simulated projectile computes a trajectory in the model. The actual projectile does not compute all possible theories of its own motion simply by moving through space. The physical system has dynamics; the model has a computational structure. Whether there is a physical computation depends on a constrained relationship between physical and abstract process categories.
This distinction is essential for avoiding pancomputationalism.
By contrast, consider a billiard-ball computer. In that case, the physical system is deliberately constrained so that collisions of idealized balls implement logical operations. The physical dynamics are organized so that the system’s state transitions correspond to abstract computational operations. The mapping is not arbitrary. It is built into the device’s structure, its boundary conditions, and its read/write interpretation. That is the kind of case where the categorical framework can describe physical computation clearly.
Toward a more precise theory of biological computation
The long-term motivation of this work is not only philosophical. It is also scientific.
Biological systems are full of organized dynamics. They regulate, adapt, signal, remember, differentiate, synchronize, oscillate, and respond to perturbations. In computational neuroscience and systems biology, we often want to know whether such systems are computing, and if so, what kind of computation they perform.
But the answer cannot be obtained by metaphor. It requires a formal account of when physical dynamics support abstract operations.
The category-theoretic framework developed in the paper is a step toward such an account. It gives us a way to examine biological systems without either reducing them prematurely to digital computers or exempting them from computational analysis altogether. It allows us to ask whether a given biological process has the compositional, causal, counterfactual, and representational structure required for computation.
This may be particularly useful for studying neural circuits, cellular regulatory systems, developmental processes, and multiscale biological organization. These systems are not merely collections of components. They are compositional physical systems with nested dynamics. Category theory is well suited to describing such systems because it treats relations, transformations, and composition as primary.
In this sense, the framework may help move the discussion from “is life computation?” or “is the brain a computer?” toward more precise questions:
Which biological processes instantiate computations?
Which abstractions preserve their physical process structure?
How do computational descriptions at different biological scales relate?
When are two biological implementations computationally equivalent?
When is a computational description merely a useful model, and when is it physically instantiated by the system?
These are the questions that a mature theory of biological computation must answer.
Conclusion
Computation is physical, but not every physical process is computation.
That sentence captures the central tension of the paper. On one hand, every real computation must be physically instantiated. There is no computation without some physical system undergoing state transitions. On the other hand, physical state transition alone is not enough. A physical system computes only when its dynamics can be mapped, in a constrained and structure-preserving way, to an abstract process.
The category-theoretic framework gives us a language for that constraint. By defining physical and abstract process categories, using functors to relate them, natural transformations to describe refinement, and adjunctions to formalize multiple realizability, we obtain a more precise account of physical computation.
This matters for foundations of computation. It matters for quantum and unconventional computing. It matters for systems biology. And it matters for computational neuroscience, where the language of computation is powerful but often under-constrained.
The goal is not to decide once and for all whether “the brain is a computer,” whether “cells compute,” or whether “the universe computes.” Those questions are too broad. The better goal is to develop a formal framework that tells us what must be true for a physical system, or part of a physical system, to count as computing.
That is the direction this paper takes: away from computation as metaphor, and toward computation as structured physical process.