Computability and Complexity of Unconventional Computing Devices

Hajo Broersma, Susan Stepney, Göran Wendin

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

    3 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
    EditorsSusan Stepney, Steen Rasmussen, Martyn Amos
    Place of PublicationCham
    PublisherSpringer
    Chapter11
    Pages185-229
    Number of pages45
    ISBN (Electronic)978-3-319-65826-1
    ISBN (Print)978-3-319-65824-7
    DOIs
    Publication statusPublished - 20 Jul 2018

    Publication series

    NameNatural Computing Series
    PublisherSpringer
    ISSN (Print)1619-7127

    Fingerprint

    Dive into the research topics of 'Computability and Complexity of Unconventional Computing Devices'. Together they form a unique fingerprint.

    Cite this