Computability and Complexity of Unconventional Computing Devices
arXiv:1702.02980
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.
to appear in "Computational Matter". Stepney, Rasmussen, Amos, eds. Springer 2017