SAD Computers and Two Versions of the Church–Turing Thesis
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.
1 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
2 Physical Computability
2.1 The Physical Church–Turing Thesis
2.2 Deterministic barriers to physical computation
2.3 Probabilistic barriers to physical computation
3 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
4 Concluding Remarks