Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Physical Computation: How General are Gandy’s Principles for Mechanisms?

  • Published:
Minds and Machines Aims and scope Submit manuscript

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.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. See Hagar and Korolev (2006, 2007) for a thorough critique of Kieu's proposed hypercomputer.

  2. Davies's construction is in fact more complex and elegant than described here, and, of course, lengthier (see 2001:672–674).

  3. See Davies for a discussion of, and an argument for, the physical plausibility of this computation (2001:677–679).

  4. See Hogarth (1994:127–133).

  5. For details see Hogarth (1992, 1994).

  6. 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 .

  7. 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.

    Article  MATH  MathSciNet  Google Scholar 

  • Copeland, B. J. (1997). The broad conception of computation. American Behavioral Scientist, 40, 690–716.

    Article  Google Scholar 

  • (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).

    Article  Google Scholar 

  • Copeland, B. J., & Sylvan, R. (1999). Beyond the universal Turing machine. Australasian Journal of Philosophy, 77, 46–66.

    Article  Google Scholar 

  • da Costa, N. C. A., & Doria, F. A. (1991). Classical physics and Penrose’s thesis. Foundations of Physics Letters, 4, 363–374.

    Article  MathSciNet  Google Scholar 

  • Davies, B. (2001). Building infinite machines. British Journal for the Philosophy of Science, 52, 671–682.

    Article  MATH  MathSciNet  Google Scholar 

  • Earman, J. (1986). A primer on determinism. Dordrecht: D. Reidel.

    Google Scholar 

  • Earman, J., & Norton, J. D. (1993). Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes. Philosophy of Science, 60, 22–42.

    Article  MathSciNet  Google Scholar 

  • Etesi, G., & Németi, I. (2002). Non-Turing computations via Malament-Hogarth space-times. International Journal of Theoretical Physics, 41, 341–370.

    Article  MATH  MathSciNet  Google Scholar 

  • 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.

    Article  Google Scholar 

  • (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.

    Article  MathSciNet  Google Scholar 

  • (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.

    Google Scholar 

  • Kieu, T. D. (2002). Quantum hypercomputation. Minds and Machines, 12, 541–561.

    Article  MATH  Google Scholar 

  • Kreisel, G. (1974). A notion of mechanistic theory. Synthese, 29, 11–26.

    Article  MATH  Google Scholar 

  • (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.

    Google Scholar 

  • Pitowsky, I. (1990). The physical Church thesis and physical computational complexity. Iyyun, 39, 81–99.

    Google Scholar 

  • 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.

    Article  MATH  MathSciNet  Google Scholar 

  • (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.

    Google Scholar 

  • Shagrir, O. (2002). Effective computation by humans and machines. Minds and Machines, 12, 221–240.

    Article  MATH  Google Scholar 

  • Shagrir, O., & Pitowsky, I. (2003). Physical hypercomputation and the Church-Turing thesis. Minds and Machines, 13, 87–101.

    Article  MATH  Google Scholar 

  • 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.

    Google Scholar 

  • Siegelmann, H. T., & Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science, 131, 331–360.

    Article  MATH  MathSciNet  Google Scholar 

  • 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).

Download references

Acknowledgment

Shagrir's research was supported by the Israel Science Foundation, grant 857/03-07.

Author information

Authors and Affiliations

  1. School of Philosophy, University of Canterbury, Private Bag 4800, Christchurch, New Zealand

    B. Jack Copeland

  2. Department of Philosophy, The Hebrew University of Jerusalem, Jerusalem, 91905, Israel

    Oron Shagrir

Authors
  1. B. Jack Copeland
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Oron Shagrir
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Oron Shagrir.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11023-007-9058-2

Keywords

Search

Navigation