Abstract
What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Davies's construction is in fact more complex and elegant than described here, and, of course, lengthier (see 2001:672–674).
See Davies for a discussion of, and an argument for, the physical plausibility of this computation (2001:677–679).
See Hogarth (1994:127–133).
One could define, of course, the previous state of T A -halting-on-0 to be the state of T B -ceasing-to-exist. But the stipulation only shifts the problem to the state of T B -ceasing-to-exist. For now the state of T B -ceasing-to-exist must be determined by a previous state. Yet there is no such state, for in between each state of T B and the state of T B -ceasing-to-exist there are infinitely many other states of T B .
With thanks to two anonymous referees for helpful comments.
References
Abramson, F.G. (1971). Effective computation over the real numbers. Twelfth annual symposium on switching and automata theory. Northridge, Calif.: Institute of Electrical and Electronics Engineers.
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.
(1998a). Super Turing-machines. Complexity, 4, 30–32.
(1998b). Even Turing machines can compute uncomputable functions. In C. Calude, J. Casti & M. Dinneen (Eds.), Unconventional models of computation. London: Springer-Verlag.
(2000). Narrow versus wide mechanism. Journal of Philosophy, 96, 5–32.
(2002a). Accelerating Turing machines. Minds and Machines, 12, 281–301.
(2002b). Hypercomputation. In B. J. Copeland (Ed.) 2002–3.
(Ed.). (2002–3). Hypercomputation. Special issue of Minds and Machines (Vols 12(4), 13(1)).
(Ed.). (2004). The essential Turing. Oxford: Oxford University Press.
(Ed.). (2005). Alan Turing’s Automatic Computing Engine: The master codebreaker’s struggle to build the modern computer. Oxford: Oxford University Press.
Copeland, B. J., & Proudfoot, D. (1999). Alan Turing’s forgotten ideas in computer science. Scientific American, 280, 76–81 (April).
Copeland, B. J., & Sylvan, R. (1999). Beyond the universal Turing machine. Australasian Journal of Philosophy, 77, 46–66.
da Costa, N. C. A., & Doria, F. A. (1991). Classical physics and Penrose’s thesis. Foundations of Physics Letters, 4, 363–374.
Davies, B. (2001). Building infinite machines. British Journal for the Philosophy of Science, 52, 671–682.
Earman, J. (1986). A primer on determinism. Dordrecht: D. Reidel.
Earman, J., & Norton, J. D. (1993). Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes. Philosophy of Science, 60, 22–42.
Etesi, G., & Németi, I. (2002). Non-Turing computations via Malament-Hogarth space-times. International Journal of Theoretical Physics, 41, 341–370.
Gandy, R. (1980). Church’s thesis and principles for mechanisms. In J. Barwise, H. J. Keisler & K. Kunen (Eds.), The Kleene symposium. Amsterdam: North-Holland.
Hagar, A., & Korolev, A. (2006). Quantum hypercomputability? Minds and Machines, 16, 87–93.
(2007). Quantum hypercomputation: Hype or computation? Philosophy of Science (forthcoming).
Hogarth, M. L. (1992). Does general relativity allow an observer to view an eternity in a finite time? Foundations of Physics Letters, 5, 173–181.
(1994). Non-Turing computers and non-Turing computability. PSA, 1, 126–138.
(2004). Deciding arithmetic using SAD computers. British Journal for the Philosophy of Science, 55, 681–691.
Israel, D. (2002). Reflections on Gödel’s and Gandy’s reflections on Turing’s thesis. Minds and Machines, 12, 181–201.
Kieu, T. D. (2002). Quantum hypercomputation. Minds and Machines, 12, 541–561.
Kreisel, G. (1974). A notion of mechanistic theory. Synthese, 29, 11–26.
(1982). Review of Pour-El and Richards. Journal of Symbolic Logic, 47, 900–902.
Penrose, R. (1994). Shadows of the mind: A search for the missing science of consciousness. Oxford: Oxford University Press.
Pitowsky, I. (1990). The physical Church thesis and physical computational complexity. Iyyun, 39, 81–99.
Pour-El, M. B., & Richards, J. I. (1979). A computable ordinary differential equation which possesses no computable solution. Annals of Mathematical Logic, 17, 61–90.
(1989). Computability in analysis and physics. Berlin: Springer.
Russell, B. A. W. (1936). The limits of empiricism. Proceedings of the Aristotelian Society, 36, 131–50.
Shagrir, O. (2002). Effective computation by humans and machines. Minds and Machines, 12, 221–240.
Shagrir, O., & Pitowsky, I. (2003). Physical hypercomputation and the Church-Turing thesis. Minds and Machines, 13, 87–101.
Sieg, W. (2002). Calculations by man & machine: Mathematical presentation. Proceedings of the Cracow international congress of logic, methodology and philosophy of science. Synthese Series, Kluwer Academic Publishers.
Sieg, W., & Byrnes, J. (1999). An abstract model for parallel computations: Gandy’s thesis. Monist, 82, 150–164.
Siegelmann, H. T., & Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science, 131, 331–360.
Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society (Series 2, Vol. 42, pp. 230–265). In Copeland B. J. (Ed.). The essential Turing, 2004.
(1945). Proposed electronic calculator. In Copeland B. J. (Ed.) Alan Turing’s Automatic Computing Engine, 2005.
(1948). Intelligent machinery. In The essential Turing.
Welch P. D. The extent of computation in Malament-Hogarth spacetimes (forthcoming).
Acknowledgment
Shagrir's research was supported by the Israel Science Foundation, grant 857/03-07.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Copeland, B.J., Shagrir, O. Physical Computation: How General are Gandy’s Principles for Mechanisms?. Minds & Machines 17, 217–231 (2007). https://doi.org/10.1007/s11023-007-9058-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11023-007-9058-2