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 helped show 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 impossible to calculate with regular computers. There are many more functions than the ones we can usually work with. These special functions go beyond what normal computers can handle.

Models

Hypercomputers are special kinds of machines that could, in theory, solve problems that regular computers cannot. These machines imagine having extra information or abilities beyond what we usually think of as computing. For example, some models suggest a machine could know the answer to questions that we cannot currently decide, like whether a certain program will ever stop running.

These ideas range from those that seem almost possible, like using very strange physical laws, to others that need impossible conditions, like having a machine that can do infinitely many steps in a finite amount of time. Some theories even explore what might happen if a computer could use special properties of quantum physics or keep trying answers until it gets the right one after an extremely 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 think that hypercomputation is not really possible. Martin Davis calls it "a myth" and says it is not something we can actually build with our current understanding of physics and mathematics. He also points out that ideas about hypercomputation are not as new as some people think.

Another person, Aran Nayebi, has also argued that, based on what we know about how the world works, hypercomputation does not seem possible. Both of these views suggest that while it is interesting to think about, hypercomputation may not be something we can actually create in real life.

Martin Davis computability theory