Physical constraints on hypercomputation

Paul Cockshott, Lewis Mackenzie, Greg Michaelson

Research output: Contribution to journalArticle

Abstract

Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. © 2007 Elsevier Ltd. All rights reserved.

Original languageEnglish
Pages (from-to)159-174
Number of pages16
JournalTheoretical Computer Science
Volume394
Issue number3
DOIs
Publication statusPublished - 8 Apr 2008

Fingerprint

resources

Keywords

  • Computability
  • Hyper-computing
  • Quantum-computing
  • Quantum-measurement

Cite this

Cockshott, Paul ; Mackenzie, Lewis ; Michaelson, Greg. / Physical constraints on hypercomputation. In: Theoretical Computer Science. 2008 ; Vol. 394, No. 3. pp. 159-174.
@article{f32a39eba3f94482b0a7271a60446708,
title = "Physical constraints on hypercomputation",
abstract = "Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. {\circledC} 2007 Elsevier Ltd. All rights reserved.",
keywords = "Computability, Hyper-computing, Quantum-computing, Quantum-measurement",
author = "Paul Cockshott and Lewis Mackenzie and Greg Michaelson",
year = "2008",
month = "4",
day = "8",
doi = "10.1016/j.tcs.2007.12.009",
language = "English",
volume = "394",
pages = "159--174",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

Physical constraints on hypercomputation. / Cockshott, Paul; Mackenzie, Lewis; Michaelson, Greg.

In: Theoretical Computer Science, Vol. 394, No. 3, 08.04.2008, p. 159-174.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Physical constraints on hypercomputation

AU - Cockshott, Paul

AU - Mackenzie, Lewis

AU - Michaelson, Greg

PY - 2008/4/8

Y1 - 2008/4/8

N2 - Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. © 2007 Elsevier Ltd. All rights reserved.

AB - Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. © 2007 Elsevier Ltd. All rights reserved.

KW - Computability

KW - Hyper-computing

KW - Quantum-computing

KW - Quantum-measurement

UR - http://www.scopus.com/inward/record.url?scp=40649100953&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2007.12.009

DO - 10.1016/j.tcs.2007.12.009

M3 - Article

VL - 394

SP - 159

EP - 174

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -