Computability and Complexity of Unconventional Computing Devices

Hajo Broersma, Susan Stepney, Göran Wendin

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.
Original languageEnglish
Title of host publicationComputational Matter
Chapter11
Pages185-229
Number of pages45
ISBN (Electronic)978-3-319-65826-1
DOIs
Publication statusE-pub ahead of print/First online - 20 Jul 2018

Publication series

NameNatural Computing Series
ISSN (Print)1619-7127

Fingerprint

Computability
Turing
Computing
Polynomial time
NP-complete problem
Resources

Cite this

Broersma, H., Stepney, S., & Wendin, G. (2018). Computability and Complexity of Unconventional Computing Devices. In Computational Matter (pp. 185-229). (Natural Computing Series). https://doi.org/10.1007/978-3-319-65826-1_11
Broersma, Hajo ; Stepney, Susan ; Wendin, Göran. / Computability and Complexity of Unconventional Computing Devices. Computational Matter. 2018. pp. 185-229 (Natural Computing Series).
@inbook{61b27d5a68424c6b9b729d0ff136fa3d,
title = "Computability and Complexity of Unconventional Computing Devices",
abstract = "We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.",
author = "Hajo Broersma and Susan Stepney and G{\"o}ran Wendin",
year = "2018",
month = "7",
day = "20",
doi = "10.1007/978-3-319-65826-1_11",
language = "English",
isbn = "978-3-319-65824-7",
series = "Natural Computing Series",
pages = "185--229",
booktitle = "Computational Matter",

}

Broersma, H, Stepney, S & Wendin, G 2018, Computability and Complexity of Unconventional Computing Devices. in Computational Matter. Natural Computing Series, pp. 185-229. https://doi.org/10.1007/978-3-319-65826-1_11

Computability and Complexity of Unconventional Computing Devices. / Broersma, Hajo; Stepney, Susan; Wendin, Göran.

Computational Matter. 2018. p. 185-229 (Natural Computing Series).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Computability and Complexity of Unconventional Computing Devices

AU - Broersma, Hajo

AU - Stepney, Susan

AU - Wendin, Göran

PY - 2018/7/20

Y1 - 2018/7/20

N2 - We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.

AB - We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.

U2 - 10.1007/978-3-319-65826-1_11

DO - 10.1007/978-3-319-65826-1_11

M3 - Chapter

SN - 978-3-319-65824-7

T3 - Natural Computing Series

SP - 185

EP - 229

BT - Computational Matter

ER -

Broersma H, Stepney S, Wendin G. Computability and Complexity of Unconventional Computing Devices. In Computational Matter. 2018. p. 185-229. (Natural Computing Series). https://doi.org/10.1007/978-3-319-65826-1_11