20
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Two famous examples: some of them have access to oracles, others can complete infinite number of steps. Both of these allow solving the halting problem for Turing machines. $\endgroup$
    – Kaveh
    Commented Apr 8, 2011 at 9:10
  • 1
    $\begingroup$ The proceedings for the conference [Comutability in Europe (CiE) 2006 in Swansea][1] should have a lot of papers on hypercomputation. [1]: cs.swan.ac.uk/cie06 $\endgroup$
    – Rob
    Commented Apr 8, 2011 at 9:16
  • 2
    $\begingroup$ You can ask the question in the reverse direction: what properties of a machine model make a TM simulation possible? and then Robin Gandy's 1980 result sheds some light on the question. Sometimes it is stated as local modifications of finite amount of information. $\endgroup$
    – Kaveh
    Commented Apr 8, 2011 at 9:24

3 Answers 3

Reset to default
11
$\begingroup$

In the paper On the power of multiplication in random access machines it has been proven by Hartmanis and Simon that, if we add unit cost multiplication instruction in a RAM (called MRAM) then for this model P = NP. In addition the languages decided in polynomial time in the MRAM model are exactly the languages in PSPACE.

As stated in the paper, this results shows that multiplication have the same complexity as addition iff P = PSPACE.

A more related result I have heard of, is that if we add a division instruction with infinite precision in a RAM then we can solve undecidable problems. However I could not find the paper that proves this result. If anyone is familiar with it please comment and I will update the answer.

Improve this answer
$\endgroup$
8
$\begingroup$

So you have discovered that TMs cannot solve every problem! The very first step Turing took and is highly logical (although not trivial if you consider the state of computing at that time) was oracles.

Informally, you are adding to your machine a new black-box module that can "somehow" solve the problem your machine cannot, let's say the halting problem. Of course, oracles are just a mathematical abstraction and there is no secret behind their inner workings. Personally, I don't see any way that an oracle can be used to discover a model that disproves the Church-Turing thesis.

  • Manipulating time and space

Since the problem with solving the halting problem is knowing when the machine is going to stop, by running the machine in a spacetime that is different from ours can allow you to solve it. From my sources when I was writing a report on models that can efficiently solved $NP$ , theoretical physicists believe that those conditions are satisfied near the edge of black holes. To do this you must have the computing machine very near the black hole but not into its event horizon (so it doesn't get pulled in). Then you dive in the black hole and you can review the whole infinite timeline of your machine in finite time. This probably means that you get pulled in the black hole, so I guess it's not going to be implemented and tested even if we could reach a black hole. This is all informal, you start reading a more theoretical physics approach from the wikipedia article on the Malament-Hogarth_spacetime. A helpful citation is also the article Does general relativity allow an observer to view an eternity in a finite time?

  • Zeno's machine could solve any problem in 2 seconds, but it is a mathematical hypothetical construction, where each step takes half the time of that before it and the first time takes 1 second. It doesn't provide a real world solution you could implement.

There are other models I know of, but I think they simply expand on the ideas I've presented here or are pure mathematical constructions, so they are more like "neat tricks" than something that could disprove the Church-Turing thesis.

Improve this answer
$\endgroup$
2
$\begingroup$

Not exactly what you asked, but Scott Aaronson has a paper, nicely explained here about Turing machines with the ability to time travel, but with self-consistency requirements (i.e. you can't go back to change the past. You can observe the future, but it must be consistent with the present).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.