Abstract
The Church-Turing thesis asserts that every effectively computable function is Turing computable. On the other hand, the physical Church-Turing Thesis (PCTT) concerns the computational power of physical systems, regardless of whether these perform effective computations. We distinguish three variants of PCTT – modest, bold and super-bold – and examine some objections to each. We highlight Itamar Pitowsky’s contributions to the formulation of these three variants of PCTT, and discuss his insightful remarks regarding their validity. The distinction between the modest and bold variants was originally advanced by Piccinini (Br J Philos Sci 62:733–769, 2011). The modest variant concerns the behavior of physical computing systems, while the bold variant is about the behavior of physical systems more generally. Both say that this behavior, when formulated in terms of some mathematical function, is Turing computable. We distinguish these two variants from a third – the super-bold variant – concerning decidability questions about the behavior of physical systems. This says, roughly, that every physical aspect of the behavior of physical systems – e.g., stability, periodicity – is decidable (i.e. Turing computable). We then examine some potential challenges to these three variants, drawn from relativity theory, quantum mechanics, and elsewhere. We conclude that all three variants are best viewed as open empirical hypotheses.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Some papers from the Workshop were published in 1990, in a special volume of Iyyun. The volume also contains papers by Avishai Margalit, Charles Parsons, Warren Goldfarb, William Tait, and Mark Steiner.
References
Aaronson, S. (2005). Guest column: NP-complete problems and physical reality. ACM SIGACT News, 36(1), 30–52.
Andréka, H., Németi, I., & Németi, P. (2009). General relativistic hypercomputing and foundation of mathematics. Natural Computing, 8, 499–516.
Barrett, J. A., & Aitken, W. (2010). A note on the physical possibility of ordinal computation. The British Journal for the Philosophy of Science, 61, 867–874.
Button, T. (2009). SAD computers and two versions of the Church-Turing thesis. The British Journal for the Philosophy of Science, 60, 765–792.
Calude, C. S., Dinneen, M. J., Dumitrescu, M., & Svozil, K. (2010). Experimental evidence of quantum randomness incomputability. Physical Review A, 82: 022102–1-022102–8.
Calude, C. S., & Svozil, K. (2008). Quantum randomness and value indefiniteness. Advanced Science Letters, 1, 165–168.
Castelvecchi, D. (2015). Paradox at the heart of mathematics makes physics problem unanswerable. Nature, 528, 207.
Chalmers, D. J. (2011). A computational foundation for the study of cognition. Journal of Cognitive Science, 12, 323–357.
Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58, 345–363.
Church, A. (1940). On the concept of a random sequence. American Mathematical Society Bulletin, 46, 130–135.
Copeland, B. J. (1997). The broad conception of computation. American Behavioral Scientist, 40, 690–716.
Copeland, B. J. (1998). Even Turing machines can compute uncomputable functions. In C. Calude, J. Casti, & M. Dinneen (Eds.), Unconventional models of computation. New York: Springer.
Copeland, B. J. (2000). Narrow versus wide mechanism. Journal of Philosophy 96, 5–32. Reprinted in M. Scheutz (Ed.) (2002). Computationalism. Cambridge, MA: MIT Press.
Copeland, B. J. (2002). Hypercomputation. Minds and Machines, 12, 461–502.
Copeland, B. J. (2004). Hypercomputation: Philosophical issues. Theoretical Computer Science, 317, 251–267.
Copeland, B. J. (2017). The Church-Turing thesis. In E. N. Zalta (Ed.),The Stanford encyclopedia of philosophy. https://plato.stanford.edu/archives/win2017/entries/church-turing/
Copeland, B. J., & Shagrir, O. (2007). Physical computation: How general are Gandy’s principles for mechanisms? Minds and Machines, 17, 217–231.
Copeland, B. J., & Shagrir, O. (2011). Do accelerating Turing machines compute the uncomputable? Minds and Machines, 21, 221–239.
Copeland, B. J., & Shagrir, O. (2019). The Church–Turing thesis—Logical limit, or breachable barrier? Communications of the ACM, 62, 66–74.
Copeland, B. J., Shagrir, O., & Sprevak, M. (2018). Zuse’s thesis, Gandy’s thesis, and Penrose’s thesis. In M. Cuffaro & S. Fletcher (Eds.), Physical perspectives on computation, computational perspectives on physics (pp. 39–59). Cambridge: Cambridge University Press.
Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015). Undecidability of the spectral gap. Nature, 528(7581), 207–211.
Davies, B. E. (2001). Building infinite machines. The British Journal for the Philosophy of Science, 52, 671–682.
Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 400(1818), 97–117.
Earman, J. (1986). A primer on determinism. Dordrecht: Reidel.
Earman, J., & Norton, J. D. (1993). Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes. Philosophy of Science, 60, 22–42.
Eisert, J., Müller, M. P., & Gogolin, C. (2012). Quantum measurement occurrence is undecidable. Physical Review Letters, 108(26), 260501.
Etesi, G., & Németi, I. (2002). Non-Turing computations via Malament-Hogarth space-times. International Journal of Theoretical Physics, 41, 341–370.
Fresco, N. (2014). Physical computation and cognitive science. Berlin: Springer.
Gandy, R. O. (1980). Church’s thesis and principles of mechanisms. In S. C. Kleene, J. Barwise, H. J. Keisler, & K. Kunen (Eds.), The Kleene symposium. Amsterdam: North-Holland.
Geroch, R., & Hartle, J. B. (1986). Computability and physical theories. Foundations of Physics, 16, 533–550.
Grzegorczyk, A. (1955). Computable functionals. Fundamenta Mathematicae, 42, 168–203.
Grzegorczyk, A. (1957). On the definitions of computable real continuous functions. Fundamenta Mathematicae, 44, 61–71.
Harel, D., & Feldman, Y. A. (1992). Algorithmics: The spirit of computing (3rd ed.). Harlow: Addison-Wesley.
Hogarth, M. (1994). Non-Turing computers and non-Turing computability. Proceedings of the Biennial Meeting of the Philosophy of Science Association, 1, 126–138.
Hogarth, M. (2004). Deciding arithmetic using SAD computers. The British Journal for the Philosophy of Science, 55, 681–691.
Komar, A. (1964). Undecidability of macroscopically distinguishable states in quantum field theory. Physical Review, second series, 133B, 542–544.
Kreisel, G. (1965). Mathematical logic. In T. L. Saaty (Ed.), Lectures on modern mathematics (Vol. 3). New York: Wiley.
Kreisel, G. (1967). Mathematical logic: What has it done for the philosophy of mathematics? In R. Schoenman (Ed.), Bertrand Russell: Philosopher of the century. London: Allen and Unwin.
Lacombe, D. (1955). Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles III. Comptes Rendus Académie des Sciences Paris, 241, 151–153.
Mazur, S. (1963). Computational analysis. Warsaw: Razprawy Matematyczne.
Miłkowski, M. (2013). Explaining the computational mind. Cambridge: MIT Press.
Moore, C. (1990). Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64, 2354–2357.
Németi, I., & Dávid, G. (2006). Relativistic computers and the Turing barrier. Journal of Applied Mathematics and Computation, 178, 118–142.
Penrose, R. (1989). The emperor’s new mind: Concerning computers, minds and the laws of physics. Oxford: Oxford University Press.
Penrose, R. (1994). Shadows of the mind. Oxford: Oxford University Press.
Piccinini, G. (2011). The physical Church-Turing thesis: Modest or bold? The British Journal for the Philosophy of Science, 62, 733–769.
Piccinini, G. (2015). Physical computation: A mechanistic account. Oxford: Oxford University Press.
Pitowsky, I. (1990). The physical Church thesis and physical computational complexity. Iyyun, 39, 81–99.
Pitowsky, I. (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.
Pitowsky, I. (2002). Quantum speed-up of computations. Philosophy of Science, 69, S168–S177.
Pour-El, M. B. (1974). Abstract computability and its relation to the general purpose analog computer (some connections between logic, differential equations and analog computers). Transactions of the American Mathematical Society, 199, 1–28.
Pour-El, M. B., & Richards, I. J. (1981). The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics, 39, 215–239.
Pour-El, M. B., & Richards, I. J. (1989). Computability in analysis and physics. Berlin: Springer.
Scarpellini, B. (1963). Zwei unentscheidbare Probleme der Analysis. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 9, 265–289. English translation in Minds and Machines 12 (2002): 461–502.
Shagrir, O. (2006). Why we view the brain as a computer. Synthese, 153, 393–416.
Shagrir, O., & Pitowsky, I. (2003). Physical hypercomputation and the Church–Turing thesis. Minds and Machines, 13, 87–101.
Sprevak, M. (2010). Computation, individuation, and the received view on representation. Studies in History and Philosophy of Science, 41, 260–270.
Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series, 2(42), 230–265.
Turing, A. M. (1947). Lecture on the Automatic Computing Engine. In Copeland, B. J. (2004). The essential Turing: Seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma. Oxford University Press.
Turing, A. M. (1948). Intelligent machinery. In The essential Turing. Oxford University Press.
Turing, A.M. (1950). Computing machinery and intelligence. In The essential Turing. Oxford University Press.
Welch, P. D. (2008). The extent of computation in Malament-Hogarth spacetimes. The British Journal for the Philosophy of Science, 59, 659–674.
Wolfram, S. (1985). Undecidability and intractability in theoretical physics. Physical Review Letters, 54, 735–738.
Acknowledgements
An early version of this chapter was presented at the Workshop on Physics and Computation (UCNC2018) in Fontainebleau, at the International Association for Computing and Philosophy meeting (IACAP2018) in Warsaw, and at the research logic seminar in Tel Aviv University. Thanks to the audiences for helpful discussion. We are also grateful to Piccinini for his comments on a draft of this paper. Shagrir’s research was supported by the Israel Science Foundation grant 830/18.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Copeland, B.J., Shagrir, O. (2020). Physical Computability Theses. In: Hemmo, M., Shenker, O. (eds) Quantum, Probability, Logic. Jerusalem Studies in Philosophy and History of Science. Springer, Cham. https://doi.org/10.1007/978-3-030-34316-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-34316-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34315-6
Online ISBN: 978-3-030-34316-3
eBook Packages: Religion and PhilosophyPhilosophy and Religion (R0)