home >
publications >
non-standard computation >
*Computability and Complexity of Unconventional Computing Devices*

### Hajo Broersma, Susan Stepney, Göran Wendin.

Computability and Complexity of Unconventional Computing Devices.

#### in Susan Stepney, Steen Rasmussen, Martyn Amos, eds, *Computational Matter*, pp.185–229. Springer, 2018

#### 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.

arXiv preprint: arXiv:1702.02980 | doi:10.1007/978-3-319-65826-1_11

@inproceedings(Broersma-CompMatter-2018,
author = "Hajo Broersma and Susan Stepney and G{\"o}ran Wendin",
title = "Computability and Complexity of Unconventional Computing Devices",
chapter = 11,
pages = "185-229",
crossref = "CompMatter-2018"
)
@proceedings(CompMatter-2018,
editor = "Susan Stepney and Steen Rasmussen and Martyn Amos",
title = "Computational Matter",
booktitle = "Computational Matter",
publisher = "Springer",
year = 2018,
)