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


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",
  title = "Computability and Complexity of Unconventional Computing Devices", 
  chapter = 11,
  pages = "185-229",
  crossref = "CompMatter-2018"

  editor = "Susan Stepney and Steen Rasmussen and Martyn Amos",
  title = "Computational Matter",
  booktitle = "Computational Matter",
  publisher = "Springer",
  year = 2018,