Skip to main content
3 of 3
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

How do models of hypercomputation overcome the Halting Problem?

Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access to a resource that allows the Halting Problem for standard Turing machines to be solved. Call this a "superpower": a hypercomputer with a superpower can decide whether any standard Turing machine terminates.

What kinds of "superpowers" do hypercomputers use?

Ed Blakey's thesis sets up a formal framework to classify some of the major kinds of resources used in hypercomputing, but it does not try to provide a comprehensive survey of superpowers. I am not interested in a list of hypercomputers (there is a nice list in the Wikipedia article), but in understanding what "special sauce" each model uses, perhaps thought of as a unique kind of resource.

This question is inspired by How fundamental is undecidability?. Also related is What would it mean to disprove Church-Turing thesis? which generated lots of interesting discussion, and Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines?.

András Salamon
  • 19.2k
  • 3
  • 65
  • 151