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

in Susan Stepney, Steen Rasmussen, Martyn Amos, eds, Computational Matter, Springer, 2017 (submitted)


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öran Wendin",
  title = "Computability and Complexity of Unconventional Computing Devices", 
  note = "submitted"
  crossref = "CompMatter-2017"

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