Abstract
This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the 'maximality thesis'), it discusses proposals for digital hypercomputing with "Zeno-machines", i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either they are specified such that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation.
Original language | English |
---|---|
Pages (from-to) | 83-96 |
Number of pages | 14 |
Journal | Minds and Machines |
Volume | 21 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Feb 2011 |
Externally published | Yes |
Keywords
- Accelerated Turing machine
- Benacerraf
- Church-Turing thesis
- Computability
- Computing
- Copeland
- Effective computing
- Hypercomputing
- Supertask
- Thomson
- Zeno
- Zeno-machine