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 - 2014 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Stanford, CA: The Metaphysics Research Lab.
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
429 (#43,674)

6 months
134 (#23,956)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Tim Button
University College London

Citations of this work

Computation in physical systems.Gualtiero Piccinini - 2010 - Stanford Encyclopedia of Philosophy.
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
The philosophy of computer science.Raymond Turner - 2013 - Stanford Encyclopedia of Philosophy.

View all 10 citations / Add more citations

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