SAD computers and two versions of the Church–Turing thesis

British Journal for the Philosophy of Science 60 (4):765-792 (2009)
  Copy   BIBTEX

Abstract

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version of the Church–Turing Thesis is unaffected by SAD computation

Similar books and articles

The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Quantum speed-up of computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Deciding arithmetic using SAD computers.Mark Hogarth - 2004 - British Journal for the Philosophy of Science 55 (4):681-691.

Analytics

Added to PP
2009-11-21

Downloads
400 (#43,734)

6 months
123 (#23,887)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Tim Button
University College London

References found in this work

The logical basis of metaphysics.Michael Dummett - 1991 - Cambridge, Mass.: Harvard University Press.
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Infinity.José A. Benardete - 1964 - Oxford,: Clarendon Press.
An Introduction to Gödel's Theorems.Peter Smith - 2007 - New York: Cambridge University Press.

View all 31 references / Add more references