Computation in Physical Systems(leibniz.stanford.edu)

Stanford Encyclopedia of Philosophy

Browse

Table of Contents
What's New
Random Entry
Chronological
Archives

About

Editorial Information
About the SEP
Editorial Board
How to Cite the SEP
Special Characters
Advanced Tools
Contact

Support SEP

Support the SEP
PDFs for SEP Friends
Make a Donation
SEPIA for Libraries

Entry Contents
Bibliography
Academic Tools
Friends PDF Preview
Author and Citation Info
Back to Top

Computation in Physical SystemsFirst published Wed Jul 21, 2010; substantive revision Wed Aug 20, 2025

In our ordinary discourse, we distinguish between physical systems
that perform computations, such as computers and calculators, and
physical systems that don’t, such as rocks. Among computing
devices, we distinguish between more and less powerful ones. These
distinctions affect our behavior: if a device is computationally more
powerful than another, we pay more money for it. What grounds these
distinctions? What is the principled difference, if there is one,
between a rock and a calculator, or between a calculator and a
computer? Answering these questions is more difficult than it may
seem.

In addition to our ordinary discourse, computation is central to many
sciences. Computer scientists design, build, and program computers.
But again, what counts as a computer? If a salesperson sold you an
ordinary rock as a computer, you should probably get your money back.
Again, what does the rock lack that a genuine computer has?

How powerful a computer can you build? Can you build a machine that
computes anything you wish? Although it is often said that modern
computers can compute anything (i.e., any function defined over a
denumerable domain, such as the natural numbers or strings of letters
from a finite alphabet), this is incorrect. Ordinary computers can
compute only a tiny subset of all functions. Is it physically possible
to do better? Which functions are physically computable? These
questions are bound up with the foundations of physics.

Computation is also central to the mind sciences, and perhaps other
areas of biology. According to the computational theory of cognition,
cognition is a kind of computation: the behavior of cognitive systems
is causally explained by the computations they perform. In order to
test a computational theory of something, we need to know what counts
as a computation in a physical system. Once again, the nature of
physical computation lies at the foundation of empirical science.

1. Abstract Computation and Concrete Computation
2. Accounts of Concrete Computation

2.1 The Simple Mapping Account
2.2 Restricted Mapping Accounts
2.3 The Semantic Account
2.4 The Syntactic Account
2.5 The Mechanistic Account

3. Is Every Physical System Computational?

3.1 Varieties of Pancomputationalism
3.2 Unlimited Pancomputationalism
3.3 Limited Pancomputationalism
3.4 The Universe as a Computing System

4. Physical Computability

4.1 The Physical Church-Turing Thesis: Bold
4.2 The Physical Church-Turing Thesis: Modest
4.3 Hypercomputation

Bibliography
Academic Tools
Other Internet Resources
Related Entries

1. Abstract Computation and Concrete Computation

Computation may be studied mathematically by formally defining
computational objects, such as algorithms and Turing machines, and
proving theorems about their properties. The mathematical theory of
computation is a well-established branch of mathematics. It deals with
computation in the abstract, without worrying much about physical
implementation.

By contrast, most uses of computation in science and ordinary practice
deal with concrete computation: computation in concrete physical
systems such as computers and brains. Concrete computation is closely
related to abstract computation: we speak of physical systems as
running an algorithm or as implementing a Turing machine, for example.
But the relationship between concrete computation and abstract
computation is not part of the mathematical theory of computation per
se and requires further investigation (cf. Curtis-Trudel 2022 for an
argument that abstract and concrete computation cannot be given a
unified account). Questions about concrete computation are the main
subject of this entry. Nevertheless, it is important to bear in mind
some basic mathematical results.

An important notion of computation is that of digital
computation, which Alan Turing, Kurt Gödel, Alonzo
Church, Emil Post, and Stephen Kleene formalized in the 1930s. Their
work investigated the foundations of mathematics. One crucial question
was whether first order logic is decidable — whether
there is an algorithm that determines whether any given first order
logical formula is a theorem.

Both Turing (1936–7) and Church (1936) proved that the answer is
negative: there is no such algorithm. To show this, they offered
precise characterizations of the informal notion of algorithmically
computable function (over a denumerable domain). Turing did so in
terms of so-called Turing machines (TMs) — devices that
manipulate discrete symbols written on a tape in accordance with
finitely many instructions. Other logicians did the same thing —
they formalized the notion of algorithmically computable function
— in terms of other notions, such as general recursive functions
and λ-definable functions.

To their surprise, all such notions turned out to be extensionally
equivalent, that is, any function computable within any of these
formalisms is computable within any of the others. This is evidence
that their quest for a precise definition of “algorithm”
or “algorithmically computable function” had been
successful. The resulting view — that TMs and other equivalent
formalisms capture the informal notion of algorithm for computing
functions over a denumerable domain — is now known as the
Church-Turing thesis (more on this in Section 4). The study of
computable functions, made possible by the work of Turing et
al., is part of the mathematical theory of computation.

The theoretical significance of Turing et al.’s notion
of computation can hardly be overstated. As Gödel pointed out (in
a lecture following one by Tarski):

Tarski has stressed in his lecture (and I think justly) the great
importance of the concept of general recursiveness (or Turing’s
computability). It seems to me that this importance is largely due to
the fact that with this concept one has for the first time succeeded
in giving an absolute definition of an interesting epistemological
notion, i.e., one not depending on the formalism chosen. (Gödel
1946, 84)

Turing also showed that there are universal TMs — machines that
can compute any function computable by any other TM. Universal TMs do
this by executing instructions that encode the behavior of the machine
they simulate. Assuming the Church-Turing thesis, universal TMs can
compute any function computable by algorithm. This result is
significant for computer science: you don’t need to build
different computers for different functions; one universal computer
will suffice to compute any computable function. Modern digital
computers are universal in this sense: they can compute any function
computable by algorithm for as long as they have time and memory.
(Strictly speaking, a universal machine has an unbounded memory,
whereas digital computer memories can be extended but not
indefinitely, so they are not unbounded.)

The above result should not be confused with the common claim that
computers can compute anything. This claim is false: another
important result of computability theory is that most functions are
not computable by TMs (and hence, by digital computers). TMs
compute functions defined over denumerable domains, such as strings of
letters from a finite alphabet. There are uncountably many such
functions. But there are only countably many TMs; you can enumerate
TMs by enumerating all lists of TM instructions. Since an uncountable
infinity is much larger than a countable one, it follows that TMs (and
hence digital computers) can compute only a tiny portion of all
functions (over denumerable domains, such as natural numbers or
strings of letters).

TMs and most modern computers are known as (classical) digital
computers, that is, computers that manipulate strings of
discrete, unambiguously distinguishable states by performing discrete
operations that are sensitive to the position of a state within the
string. Digital computers are sometimes contrasted with
analog computers, which manipulate variables that
can be continuous via operations such as integration and
differentiation. Continuous variables are variables that can change
their value continuously over time while taking any value within a
certain interval. Analog computers are used primarily to solve certain
systems of differential equations (Pour-El 1974, Rubel 1993).

Classical digital computers may also be contrasted with
quantum computers. Quantum computers manipulate
quantum states called qudits (usually binary qudits, known as
qubits). Unlike the computational states of digital computers, qubits
are not unambiguously distinguishable from one another. This entry
will focus primarily on classical computation. For more on quantum
computation, see the
entry on quantum computing.

The same objects studied in the mathematical theory of computation
— TMs, algorithms, and so on — are typically said to be
implemented by concrete physical systems. This poses a problem: how
can a concrete, physical system perform a computation when computation
is defined by an abstract mathematical formalism? This may be called
the problem of computational implementation.

The problem of computational implementation may be formulated in a
couple of different ways. Platonists interpret the formalisms of
computability theory as defining abstract objects. According
to platonists, TMs, algorithms, and the like are abstract objects. But
how can a concrete physical system implement an abstract object?
Non-platonists treat the formalisms of computability theory as
abstract computational descriptions. But how can a concrete
physical system satisfy an abstract computational description in a way
that turns it into a system that performs the computation defined by
the computational description? Regardless of how the problem of
computational implementation is formulated, solving it requires an
account of concrete computation — an account of what it takes
for a physical system to implement a given computation.

A closely related problem is that of distinguishing between physical
systems such as digital computers, which appear to compute, and
physical systems such as rocks, which appear not to compute. Unlike
computers, ordinary rocks are not sold in computer stores and are
usually not considered computers. Why? What do computers have that
rocks lack, such that computers compute and rocks don’t? (If
indeed they don’t?) In other words, what properties must a
physical system have to implement computations? Different answers to
these questions give rise to different accounts of concrete
computation.

Questions on the nature of concrete computation should not be confused
with questions about computational modeling. The dynamical evolution
of many physical systems may be described by computational models
— computer programs that simulate the dynamics of a system. The
behavior of rocks — as well as rivers, ecosystems, and planetary
systems, among many others — may well be modeled
computationally. It doesn’t follow that the modeled systems are
computing devices — that they themselves perform computations.
Prima facie, only relatively few and quite special systems compute.
Explaining what makes them special — or explaining away our
feeling that they are special — is the job of an account of
concrete computation.

2. Accounts of Concrete Computation

Consider a mathematically defined computational system undergoing a
state transition, s1 →
s2, and a concrete physical system undergoing a
state transition, p1 →
p2. What must be the case for
p1 → p2 to implement
s1 → s2? Different
accounts give different answers.

2.1 The Simple Mapping Account

One of the earliest and most influential accounts of computation, due
to Hilary Putnam (1960/1975a, 365; 1967/1975a, 433–4), was
dubbed the “simple mapping account” by Godfrey-Smith
(2009). To a first approximation, the account says that anything that
is accurately described by a computational description C is a
computing system implementing C. More precisely, a physical
system S performs computation C just in case (i)
there is a mapping from the states ascribed to S by a
physical description to the states defined by computational
description C, such that (ii) the state transitions between
the physical states, such as p1 →
p2, mirror the state transitions between the
computational states, such as s1 →
s2. Clause (ii) requires that for any
computational state transition of the form s1
→ s2 (specified by the computational
description C), if the system is in a physical state that
maps onto s1, it then goes into a physical state
that maps onto s2.

One difficulty with the formulation above is that ordinary physical
descriptions, such as systems of differential equations, generally
ascribe uncountably many states to physical systems, whereas ordinary
computational descriptions, such as TMs tables, ascribe at most
countably many states. Thus, there are not enough computational states
for the physical states to map onto. One solution to this problem is
to reverse the direction of the mapping, requiring a mapping of the
computational states onto (a subset of) the physical states. A more
common solution — often left implicit — is to select
either a subset of the physical states or equivalence classes of the
physical states and map those onto the computational states. When this
is done, clause (i) is replaced by the following: (i′) there is
a mapping from a subset of (or equivalence classes
of) the states ascribed to S by a physical description
to the states defined by computational description C.

The simple mapping account turns out to be very liberal: it attributes
many computations to many systems. In the absence of restrictions on
which mappings are acceptable, such mappings are relatively easy to
come by. As a consequence, some have argued that every physical system
of enough complexity implements every computation from a broad class
(Putnam 1988, Searle 1992). This thesis, which trivializes the claim
that something is a computing system, will be discussed in Section
3.1. Meanwhile, the desire to avoid this trivialization result is one
motivation behind other accounts of concrete computation.

2.2 Restricted Mapping Accounts

One way to construct accounts of computation that are more restrictive
than the simple mapping account is to constrain acceptable mappings.
As we’ve seen, according to the simple mapping account, clause
(ii) requires that for any computational state transition of the form
s1 → s2 (specified by a
computational description), if the system is in a physical state that
maps onto s1, it then goes into a physical state
that maps onto s2. That second part of (ii) is a
material conditional. It may be strengthened by turning it into a
logically stronger conditional — specifically, a conditional
expressing a relation that supports counterfactuals.

In a pure counterfactual account, clause (ii) is strengthened simply
by requiring that the physical state transitions support certain
counterfactuals (Block 1978, Maudlin 1989, Copeland 1996, Rescorla
2014; Campbell and Yang 2021). In other words, a pure counterfactual
account requires the mapping between computational and physical
descriptions to be such that the counterfactual relations between the
physical states be isomorphic to the counterfactual relations between
the computational states. These counterfactuals are not satisfied by
the material conditional of clause (ii) as it appears in the simple
mapping account of computation. Thus, counterfactual accounts are
stronger than the simple mapping account.

An account of concrete computation in which the physical state
transitions support counterfactuals may also be generated by appealing
to causal, nomic, or dispositional relations, assuming (as most people
do) that causal, nomic, or dispositional relations support
counterfactuals. Appealing to causation or dispositions may also have
advantages over pure counterfactual accounts in blocking unwanted
computational implementations (Klein 2008, 145, makes the case for
dispositional versus counterfactual accounts).

In a causal account, clause (ii) is strengthened by requiring a causal
relation between the physical states: for any computational state
transition of the form s1 →
s2 (specified by a computational description), if
the system is in a physical state that maps onto
s1, its physical state causes it to go
into a physical state that maps onto s2 (Chrisley
1995, Chalmers 1995, 1996, 2011, Scheutz 1999, 2001).

To this causal constraint on acceptable mappings, David Chalmers
(1995, 1996, 2011) adds a further restriction (in order to avoid
unlimited pancomputationalism, which is discussed in Section 3): a
genuine physical implementation of a computational system must divide
into separate physical components, each of which maps onto the
components specified by the computational formalism. As Godfrey-Smith
(2009, 293) notes, this combination of a causal and a
localizational constraint goes in the direction of
mechanistic explanation (Machamer, Darden, and Craver 2000). Accounts
of computation that are explicitly based on mechanistic explanation
will be discussed in Section 2.5. For now, the causal account
simpliciter requires only that the mappings between physical and
computational descriptions be such that the causal relations between
the physical states are isomorphic to the relations between state
transitions specified by the computational description. In this sense,
according to the causal account, concrete computation is the causal
structure of a physical process.

In a dispositional account, clause (ii) is strengthened by requiring a
dispositional relation between the physical states: for any
computational state transition of the form s1
→ s2 (specified by a computational
description), if the system is in a physical state that maps onto
s1, the system manifests a disposition
whose manifestation is the transition from the physical state that
maps onto s1 to a physical state that maps onto
s2 (Klein 2008). In other words, the dispositional
account requires the mapping between computational and physical
descriptions to be such that the dispositional relations between the
physical states be isomorphic to the relations between state
transitions specified by the computational description. Thus,
according to the dispositional account, concrete computation is the
dispositional structure of a physical process.

Other restricted mapping accounts may restrict clause (ii) by
requiring that the physical state transitions mapping onto
computational state transitions be lawful (Stabler 1987), that
mappings between physical and computational transitions minimize the
length of the shortest program that can return a computational
description given a physical description (Millhouse 2019), or that
physical states that map onto computational states be predictive of
the computational transitions (Horsman et al. 2014; 2018; cf. Fletcher
2018).

The difference between the simple mapping account and restrictive
mapping accounts may be seen by examining a simple example.

Consider a rock under the sun, early in the morning. During any time
interval, the rock’s temperature rises. The rock goes from
temperature T to temperature T+1, to T+2,
to T+3. Now consider a two-state automaton that alternates
between its two states (call them 0 and 1) on each computational step,
which will be loosely called a ‘NOT gate with feedback’
hereafter for simplicity. At first, suppose the NOT gate receives
‘0’ as an input; it then returns a ‘1’. After
the ‘1’ is fed back to the NOT gate, the gate returns a
‘0’ again, and so on. The NOT gate goes back and forth
between outputting a ‘0’ and outputting a ‘1’.
Now map physical states T and T+2 onto
‘0’; then map T+1 and T+3 onto
‘1’.

According to the simple mapping account, the rock implements a NOT
gate with feedback undergoing the computation represented by
‘0101’.

By contast, according to the counterfactual account, the rock’s
putative computational implementation is spurious, because the
physical state transitions do not support counterfactuals. If the rock
were put in state T, it may or may not transition into
T+1 depending on whether it is morning or evening and other
extraneous factors. Since the rock’s physical state transitions
that map onto the NOT gate’s computational state transitions do
not support counterfactuals, the rock does not implement the NOT gate
with feedback according to the counterfactual account.

According to the causal and dispositional accounts too, this putative
computational implementation is spurious, because the physical state
transitions are not due to causal or dispositional properties of the
rock and its states. T does not cause T+1, nor does
the rock have a disposition to go into T+1 when it is in
T. Rather, the rock changes its state due to the action of
the sun. Since the rock’s physical state transitions that map
onto the NOT gate’s computational state transitions are not
grounded in either the causal or dispositional properties of the rock
and its states, the rock does not implement the NOT gate with feedback
according to the causal and dispositional accounts.

Importantly, under the above family of restrictive mapping accounts,
there are mappings between any physical system and at least some
computational descriptions. Thus, according to these accounts,
everything performs at least some computations (cf. Section 3.2). This
still strikes some as overly inclusive. In computer science and
cognitive science, there seems to be a distinction between systems
that compute and systems that do not.

To account for this distinction, Anderson and Piccinini (2024) propose
a “robust mapping account” based on three precise mapping
restrictions that are independently motivated by physical information
theory. First, if a physical system P is to implement a
computational system defined by computational description C,
it must possess physical states that map onto all
computational states defined by C — more precisely,
there must be physical states belonging to subsystems of P
that map onto each value of each variable defined by C.
Second, if p1 and p2 are
physical states that map onto computational states
s1 and s2, respectively, then
the physical state transition p1 →
p2 must map onto the computational state
transition s1 → s2.
Finally, and most significantly, for any computational state
s defined by C, each physical state that maps onto
s must be equally informative about the computational
trajectory of the system as is s. In other words, it should
not be possible to infer either more or less about the computational
evolution of the system by knowing which particular physical state the
system is in than one could infer by knowing the computational state
onto which that physical state maps. This robustness condition
generalizes on a faithfulness requirement proposed by Ladyman et al.
(2007). In our example of the rock under the sun, knowing the
temperature of the rock allows one to infer whether it is
transitioning into the first occurrence of ‘1’, the first
occurrence of ‘0’, the second occurrence of
‘1’, and so forth, which is a lot more than what can be
inferred by knowing that the input was ‘0’ or
‘1’. Thus, a rock does not implement a NOT gate with
feedback by laying under the sun. By similar reasoning, Anderson and
Piccinini (2024) argue that many mappings that count as computational
implementations under other restricted mapping accounts are not robust
enough for physical systems to bear the physical signature of any
computation. To bear the physical signature of a computation, they
argue, a physical system must satisfy the three conditions they
propose.

2.3 The Semantic Account

In our everyday life, we usually employ computations to process
meaningful symbols, in order to extract information from them. The
semantic account of computation turns this practice into a
metaphysical doctrine: computation is the processing of
representations — or at least, the processing of appropriate
representations in appropriate ways. Opinions as to which
representational manipulations constitute computations vary a great
deal (Fodor 1975, Cummins 1983, Pylyshyn 1984, Churchland and
Sejnowski 1992, Shagrir 2006, 2022, Sprevak 2010). What all versions
of the semantic account have in common is that, in a slogan, there is
“no computation without representation” (Fodor 1981,
180).

The semantic account may be seen as imposing a further restriction on
acceptable mappings. In addition to the restriction(s) imposed by
restricted mapping accounts, the semantic account imposes a semantic
restriction. Only physical states that qualify as representations may
be mapped onto computational descriptions, thereby qualifying as
computational states. If a state is not representational, it is not
computational either.

The semantic account is popular in philosophy of mind, because it
appears to fit some of its specific needs better than other accounts.
Since minds and digital computers are generally assumed to manipulate
(the right kind of) representations, they turn out to compute. Since
most other systems are generally assumed not to manipulate
(the relevant kind of) representations, they do not compute. Thus, the
semantic account appears to accommodate some common intuitions about
what does and does not count as a computing system. It keeps minds and
computers in while leaving most everything else out, thereby
vindicating the computational theory of cognition as a strong and
nontrivial theory.

The semantic account raises three important questions: how
representations are to be individuated, what counts as a
representation of the relevant kind, and what gives representations
their semantic content.

On the individuation of computational states, the main debate divides
internalists from externalists. According to externalists,
computational vehicles are symbols individuated by their wide
cognitive contents — paradigmatically, the things that
the symbols stand for (Burge 1986, Shapiro 1997, Shagrir 2001). In
contrast, most internalists maintain that computational vehicles are
symbols individuated by narrow cognitive contents (Segal
1991). Narrow contents are, roughly speaking, semantic contents
defined in terms of intrinsic properties of the system.
Cognitive contents, in turn, are contents ascribed to a
system by a cognitive psychological theory. For instance, the
cognitive contents of the visual system are visual contents, whereas
the cognitive contents of the auditory system are auditory
contents.

To illustrate the dispute, consider two physically identical cognitive
systems A and B. Among the symbols processed by
A is symbol S. A produces instances of
S whenever A is in front of bodies of water, when
A is thinking of water, and when A is forming plans
to interact with water. In short, symbol S appears to stand
for water. Every time A processes S, system
B processes symbol S′, which is physically
identical to S. But system B lives in an environment
different from A’s environment. Whenever A is
surrounded by water, B is surrounded by twater.
Twater is a substance superficially indistinguishable from water but
in fact physically different from it. Thus, symbol S′
appears to stand for twater (cf. Putnam 1975b). So, we are assuming
that A and B live in relevantly different
environments, such that S appears to stand for water while
S′ appears to stand for twater. We are also assuming
that A is processing S in the same way that
B is processing S′. There is no intrinsic
physical difference between A and B.

According to externalists, when A is processing S
and B is processing S′ they are in
computational states of different types. According to
internalists, A and B are in computational states of
the same type. In other words, externalists maintain that
computational states are individuated in part by their reference,
which is determined at least in part independently of the intrinsic
physical properties of cognitive systems. By contrast, internalists
maintain that computational states are individuated in a way that
supervenes solely on the intrinsic physical properties of cognitive
systems.

So far, externalists and internalists agree on one thing:
computational states are individuated by cognitive contents.
This assumption can be resisted without abandoning the semantic
account of computation. According to Egan (1999, 2025), computational
vehicles are not individuated by cognitive contents of any kind,
whether wide or narrow. Rather, they are individuated by their
mathematical contents — that is, mathematical functions
and objects ascribed as semantic contents to the computational
vehicles by a computational theory of the system. Since mathematical
contents are the same across physical duplicates, Egan maintains that
her mathematical contents are a kind of narrow content — she is
a kind of internalist.

Let us now turn to what counts as a representation. This debate is
less clearly delineated. According to some authors, only structures
that have a language-like combinatorial syntax, which supports a
compositional semantics, count as computational vehicles, and only
manipulations that respect the semantic properties of such structures
count as computations (Fodor 1975, Pylyshyn 1984). This suggestion
flies in the face of computability theory, which imposes no such
requirement on what counts as a computational vehicle. Other authors
are more inclusive on what representational manipulations count as
computations, but