1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1086/341843
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 58,744
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
21 Undecidability and Intractability in Theoretical Physics.Stephen Wolfram - 2013 - Emergence: Contemporary Readings in Philosophy and Science.

View all 14 references / Add more references

Citations of this work BETA

The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.
Reconsidering No-Go Theorems From a Practical Perspective.Michael E. Cuffaro - 2018 - British Journal for the Philosophy of Science 69 (3):633-655.
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.

View all 12 citations / Add more citations

Similar books and articles


Added to PP index

Total views
97 ( #105,266 of 2,425,253 )

Recent downloads (6 months)
1 ( #547,705 of 2,425,253 )

How can I increase my downloads?


My notes