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: http://dx.doi.org/10.1093/bjps/axp038
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

GO

Show Summary Details

Preview

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

Physical Computability 2.1

The Physical Church–Turing Thesis

2.2

Deterministic barriers to physical computation

2.3

Probabilistic barriers to physical computation

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

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.