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,
)