Hypercomputation

Hypercomputation, also known as super-Turing computation, explores ideas about machines that could do things regular computers cannot. These special machines might solve problems that are currently impossible to solve with today’s technology.

For example, a hypercomputer could figure out if a program will ever stop running, a question that cannot be answered by regular computers.

The Church–Turing thesis tells us that any problem a person can solve with a pencil and paper, following steps, can also be solved by a regular computer, called a Turing machine. Hypercomputers go beyond this idea. They could handle problems that are too complex for regular computers.

While some types of hypercomputation involve randomness, most studies look at machines that follow exact steps to solve problems that are not possible for regular computers. These ideas help scientists understand the limits of what computers can do and imagine new ways to solve very difficult questions.

History

A computational model that goes beyond regular machines was introduced by Alan Turing in his 1938 PhD dissertation Systems of Logic Based on Ordinals. In this paper, he explored mathematical systems where an oracle could solve special problems that normal machines cannot. This showed that even with these more powerful tools, some things still cannot be decided. Turing's oracle machines are just ideas and cannot actually be built.

State space

Most functions are too hard to calculate with regular computers. There are many more functions than the ones we usually work with. These special functions go beyond what normal computers can handle.

Models

Hypercomputers are special machines that might solve problems regular computers cannot. These machines imagine having extra abilities beyond normal computing. For example, some models suggest a machine could know the answer to questions we cannot decide, like whether a program will ever stop running.

These ideas range from those that seem almost possible, like using strange physical laws, to others that need impossible conditions, like a machine doing infinitely many steps in a finite time. Some theories explore what might happen if a computer could use special properties of quantum physics or keep trying answers for a very long time.

Analysis of capabilities

Many ideas about hypercomputation suggest new ways to use special tools, like an oracle or advice function, in regular machines. These tools could help solve problems that normal computers cannot. Some machines, called supertasking Turing machines, could handle more complex tasks by using higher levels of the arithmetic hierarchy.

Other ideas, like limiting-recursion, focus on computing specific types of problems or functions. These methods can work with tasks in the Turing degree, which includes certain levels like Δ 2 0 {\displaystyle \Delta _{2}^{0}} !{\displaystyle \Delta _{2}^{0}} . Some studies show that limiting partial recursion can solve problems in Σ 2 0 {\displaystyle \Sigma _{2}^{0}} !{\displaystyle \Sigma _{2}^{0}} .

Model	Computable predicates
supertasking	tt ⁡ ( Σ 1 0 , Π 1 0 ) {\displaystyle \operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)}
limiting/trial-and-error	Δ 2 0 {\displaystyle \Delta _{2}^{0}}
iterated limiting (k times)	Δ k + 1 0 {\displaystyle \Delta _{k+1}^{0}}
Blum–Shub–Smale machine
Malament–Hogarth spacetime	HYP
analog recurrent neural network	Δ 1 0 [ f ] {\displaystyle \Delta _{1}^{0}[f]}
infinite time Turing machine	A Q I {\displaystyle AQI}
classical fuzzy Turing machine	Σ 1 0 ∪ Π 1 0 {\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}
increasing function oracle	Δ 1 1 {\displaystyle \Delta _{1}^{1}}
ordinal turing machine	Δ 2 1 {\displaystyle \Delta _{2}^{1}}

Criticism

Some people believe that hypercomputation might not be possible. Martin Davis calls it "a myth" and says we cannot build it with what we know today about physics and mathematics. He also says that ideas about hypercomputation are not as new as some people think.

Aran Nayebi also thinks that, based on how the world works, hypercomputation does not seem possible. Both of these ideas suggest that while it is interesting to think about, hypercomputation may not be something we can actually create.

Martin Davis computability theory

Hypercomputation