Journal Article

SAD Computers and Two Versions of the Church–Turing Thesis

Tim Button

in The British Journal for the Philosophy of Science

Published on behalf of British Society for the Philosophy of Science

Volume 60, issue 4, pages 765-792
Published in print December 2009 | ISSN: 0007-0882
Published online September 2009 | e-ISSN: 1464-3537 | DOI:
SAD Computers and Two Versions of the Church–Turing Thesis

More Like This

Show all results sharing these subjects:

  • Philosophy of Science
  • Science and Mathematics


Show Summary Details


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


Avoiding supertasks


Davies's model of SAD computation


Hogarth's model of SAD computation


Generalizing SAD computers

Physical Computability 2.1

The Physical Church–Turing Thesis


Deterministic barriers to physical computation


Probabilistic barriers to physical computation

Effective Computability 3.1

The Effective Church–Turing Thesis


Hogarth's challenge to the Effective Church–Turing Thesis


Arguing from SAD computability is a non-sequitur


SAD computability is built from finitary computability

Concluding Remarks

Journal Article.  11663 words.  Illustrated.

Subjects: Philosophy of Science ; Science and Mathematics

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.