Computability and Complexity of Unconventional Computing Devices

DOI10.1007/978-3-319-65826-1_11MaRDI QIDQ3295750zbMATH OpenOpenAlexFDO

Authors Susan Stepney, Göran Wendin, Hajo Broersma

Publication date 10 July 2020

Published in Natural Computing Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.02980

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09)

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.

Recommendations

• Unconventional complexity measures for unconventional computers
• Unconventional Models of Computation Through Non-standard Logic Circuits
• Unconventional computing
• On One Unconventional Framework for Computation
• scientific article; zbMATH DE number 5883934
• scientific article; zbMATH DE number 1909825
• scientific article; zbMATH DE number 1405577
• Advances in unconventional computing. Volume 1. Theory

Cited in

(7)

• Unconventional complexity measures for unconventional computers
• scientific article; zbMATH DE number 5883934 (Why is no real title available?)
• On One Unconventional Framework for Computation
• Is universal computation a myth?
• How Redundant Is Your Universal Computation Device?
• Theory and Applications of Models of Computation
• Unbounded hardware is equivalent to deterministic Turing machines

This page was built for publication: Computability and Complexity of Unconventional Computing Devices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3295750)