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)


    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
    Number of pages45
    ISBN (Electronic)978-3-319-65826-1
    Publication statusE-pub ahead of print/First online - 20 Jul 2018

    Publication series

    NameNatural Computing Series
    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