-->

Computation in Physical Systems (Stanford Encyclopedia of Philosophy)

Stanford Encyclopedia of Philosophy

Menu

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 Navigation

Entry Contents

Bibliography

Academic Tools

Friends PDF Preview

Author and Citation Info

Back to Top

Computation in Physical Systems<br>First published Wed Jul 21, 2010; substantive revision Wed Aug 20, 2025

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

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

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

Computation is also central to the mind sciences, and perhaps other<br>areas of biology. According to the computational theory of cognition,<br>cognition is a kind of computation: the behavior of cognitive systems<br>is causally explained by the computations they perform. In order to<br>test a computational theory of something, we need to know what counts<br>as a computation in a physical system. Once again, the nature of<br>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<br>computational objects, such as algorithms and Turing machines, and<br>proving theorems about their properties. The mathematical theory of<br>computation is a well-established branch of mathematics. It deals with<br>computation in the abstract, without worrying much about physical<br>implementation.

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

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

Both Turing (1936–7) and Church (1936) proved that the answer is<br>negative: there is no such algorithm. To show this, they offered<br>precise characterizations of the informal notion of...