The British Journal for the Philosophy of Science Advance Access originally published online on September 11, 2009
The British Journal for the Philosophy of Science 2009 60(4):765-792; doi:10.1093/bjps/axp038
| ||||||||||||||||||||||||||||||||||||||||||||||||
SAD Computers and Two Versions of the Church–Turing Thesis
Darwin College, Cambridge University CB3 9EU, UK button{at}cantab.net
 |
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.
- SAD Computability
- 1.1 The basic idea of SAD computation
- 1.2 Avoiding supertasks
- 1.3 Davies's model of SAD computation
- 1.4 Hogarth's model of SAD computation
- 1.5 Generalizing SAD computers
- 1.2 Avoiding supertasks
- 1.1 The basic idea of SAD computation
- Physical Computability
- 2.1 The Physical Church–Turing Thesis
- 2.2 Deterministic barriers to physical computation
- 2.3 Probabilistic barriers to physical computation
- 2.2 Deterministic barriers to physical computation
- 2.1 The Physical Church–Turing Thesis
- Effective Computability
- 3.1 The Effective Church–Turing Thesis
- 3.2 Hogarth's challenge to the Effective Church–Turing Thesis
- 3.3 Arguing from SAD computability is a non-sequitur
- 3.4 SAD computability is built from finitary computability
- 3.2 Hogarth's challenge to the Effective Church–Turing Thesis
- 3.1 The Effective Church–Turing Thesis
- Concluding Remarks