SAD Computers and Two Versions of the Church–Turing Thesis
Tim W Button · The British Journal for the Philosophy of Science · 2009
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 Computability1.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 Computability2.1 The Physical Church–Turing Thesis 2.2 Deterministic barriers to physical computation 2.3 Probabilistic barriers to physical computation 3 Effective Computability3.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