David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers
Proceedings of the Philosophy of Science Association 2002 (3):S168-S177 (2002)
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 signiﬁcance. 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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Michael R. Garey & David S. Johnson (1983). Computers and Intractability. A Guide to the Theory of NP-Completeness. Journal of Symbolic Logic 48 (2):498-500.
Stephen Wolfram (forthcoming). 21 Undecidability and Intractability in Theoretical Physics. Emergence: Contemporary Readings in Philosophy and Science.
John Earman & John D. Norton (1993). Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes. Philosophy of Science 60 (1):22-42.
O. Shagrir & I. Pitowsky (forthcoming). The Church-Turing Thesis and Hyper-Computation. Minds and Machines.
I. Pitowsky (1996). Laplace's Demon Consults an Oracle: The Computational Complexity of Prediction. Studies in History and Philosophy of Science Part B 27 (2):161-180.
Citations of this work BETA
Michael E. Cuffaro (forthcoming). On the Significance of the Gottesman-Knill Theorem. British Journal for the Philosophy of Science:axv016.
Amit Hagar (2007). Quantum Algorithms: Philosophical Lessons. Minds and Machines 17 (2):233-247.
Amit Hagar & Alex Korolev (2007). Quantum Hypercomputation—Hype or Computation? Philosophy of Science 74 (3):347-363.
Similar books and articles
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Edwin J. Beggs, José Félix Costa & John V. Tucker (2010). Physical Oracles: The Turing Machine and the Wheatstone Bridge. Studia Logica 95 (1/2):279 - 300.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
Tim Button (2009). SAD Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
Gualtiero Piccinini (2011). The Physical Church–Turing Thesis: Modest or Bold? British Journal for the Philosophy of Science 62 (4):733 - 769.
Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Oron Shagrir & Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Added to index2009-01-28
Total downloads55 ( #81,476 of 1,934,456 )
Recent downloads (6 months)12 ( #44,741 of 1,934,456 )
How can I increase my downloads?