Computability and complexity of unconventional computing devices

• 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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Engineering (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)

Keyword

quantum optics

Quantum annealer

Quantum computers

Publication and Content Type

kap (subject category)

vet (subject category)