Computability and Complexity of Unconventional Computing Devices

Hajo Broersma; Susan Stepney; Goran Wendin

doi:10.48550/arXiv.1702.02980

Computability and Complexity of Unconventional Computing Devices

Hajo Broersma
, Susan Stepney
, Goran Wendin

Formal Methods and Tools

Research output: Working paper › Preprint › Academic

214 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 language	English
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.1702.02980
Publication status	Published - 9 Feb 2017

Keywords

cs.ET

Access to Document

10.48550/arXiv.1702.02980

1702.02980v2Final published version, 858 KB

Computability and Complexity of Unconventional Computing Devices
Broersma, H., Stepney, S. & Wendin, G., 20 Jul 2018, Computational Matter. Stepney, S., Rasmussen, S. & Amos, M. (eds.). Cham: Springer, p. 185-229 45 p. (Natural Computing Series).
Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review
5 Link opens in a new tab Citations (Scopus)

6 Downloads (Pure)

Cite this

@techreport{d958a9826b00490c9153872e95d71814,

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. ",

keywords = "cs.ET",

author = "Hajo Broersma and Susan Stepney and Goran Wendin",

note = "to appear in {"}Computational Matter{"}. Stepney, Rasmussen, Amos, eds. Springer 2017",

year = "2017",

month = feb,

day = "9",

doi = "10.48550/arXiv.1702.02980",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Computability and Complexity of Unconventional Computing Devices

AU - Broersma, Hajo

AU - Stepney, Susan

AU - Wendin, Goran

N1 - to appear in "Computational Matter". Stepney, Rasmussen, Amos, eds. Springer 2017

PY - 2017/2/9

Y1 - 2017/2/9

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.

KW - cs.ET

U2 - 10.48550/arXiv.1702.02980

DO - 10.48550/arXiv.1702.02980

M3 - Preprint

BT - Computability and Complexity of Unconventional Computing Devices

PB - ArXiv.org

ER -

Computability and Complexity of Unconventional Computing Devices

Abstract

Keywords

Access to Document

Fingerprint

Research output

Computability and Complexity of Unconventional Computing Devices

Cite this