On the possibilities of hypercomputing supertasks

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)83-96
Number of pages14
JournalMinds and Machines
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Feb 2011
Externally publishedYes

Keywords

  • Accelerated Turing machine
  • Benacerraf
  • Church-Turing thesis
  • Computability
  • Computing
  • Copeland
  • Effective computing
  • Hypercomputing
  • Supertask
  • Thomson
  • Zeno
  • Zeno-machine

Fingerprint Dive into the research topics of 'On the possibilities of hypercomputing supertasks'. Together they form a unique fingerprint.

  • Cite this