Skip to main content
No AccessArticle

SAD Computers and Two Versions of the Church–Turing Thesis

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.

1SAD Computability

1.1The basic idea of SAD computation

1.2Avoiding supertasks

1.3Davies's model of SAD computation

1.4Hogarth's model of SAD computation

1.5Generalizing SAD computers

2Physical Computability

2.1The Physical Church–Turing Thesis

2.2Deterministic barriers to physical computation

2.3Probabilistic barriers to physical computation

3Effective Computability

3.1The Effective Church–Turing Thesis

3.2Hogarth's challenge to the Effective Church–Turing Thesis

3.3Arguing from SAD computability is a non-sequitur

3.4SAD computability is built from finitary computability

4Concluding Remarks