Computability and Complexity of Unconventional Computing Devices

Hajo Broersma, Susan Stepney, Göran Wendin

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    2 Citations (Scopus)
    1 Downloads (Pure)

    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.
    Original languageEnglish
    Title of host publicationComputational Matter
    Chapter11
    Pages185-229
    Number of pages45
    ISBN (Electronic)978-3-319-65826-1
    DOIs
    Publication statusE-pub ahead of print/First online - 20 Jul 2018

    Publication series

    NameNatural Computing Series
    ISSN (Print)1619-7127

      Fingerprint

    Cite this

    Broersma, H., Stepney, S., & Wendin, G. (2018). Computability and Complexity of Unconventional Computing Devices. In Computational Matter (pp. 185-229). (Natural Computing Series). https://doi.org/10.1007/978-3-319-65826-1_11