SAD Computers and Two Versions of the Church–Turing Thesis
Bibliographic Data
| ID | 8399670 |
|---|---|
| Authors | Tim Button (0000-0001-8913-0968, University of Cambridge, corresponding author) |
| Year | 2009 |
| Volume | 60 |
| Issue | 4 |
| Pages | 765-792 |
| Publication date | 2009-12-01 |
| Peer Reviewed | Yes |
| Open Access | No |
| Type | ARTICLE |
| Venue | The British Journal for the Philosophy of Science (JOURNAL) |
| Journal identifiers | ISSN: 0007-0882 • E-ISSN: 1464-3537 |
| Publisher | Oxford University Press (PUBLISHER • GB) |
| DOI | 10.1093/bjps/axp038 |
| OpenAlex | W1989809102 |
| Language | EN |
| Citations received | 6 |
| References cited | 12 |
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
Algorithm · Computability · Computability theory · Computation · Description number · Euclidean geometry · Non-deterministic Turing machine · Probabilistic logic · Programming language · Super-recursive algorithm · Turing · Turing machine · Universal Turing machine · Artificial Intelligence · Cellular Automata and Applications · Computability, Logic, AI Algorithms · Computer Science · Mathematics · Quantum Mechanics and Applications · Theoretical Computer Science
| Unique citing works | 6 |
|---|---|
| Citations per year | 0,38 |
| Citation span | 2010 - 2024 (15) |
| Citation velocity | recent |
| Highly cited | No |
| Citation types | Neutral: 5 |