SafekipediaHypercomputation, also known as super-Turing computation, explores the idea of computers that can do things regular computers cannot. These special computers could solve problems that are currently impossible for us to solve with today’s technology. For example, a hypercomputer might be able to tell us whether a program will ever stop running—a problem known as the halting problem—or it could decide every mathematical statement in Peano arithmetic, which is a system for understanding numbers.
The Church–Turing thesis tells us that any problem that can be solved by a mathematician with a pencil and paper, using a set of steps, can also be solved by a regular computer, called a Turing machine. Hypercomputers go beyond this idea. They could perform tasks that even a Turing machine cannot, solving problems that are not computable in the usual sense.
While some forms of hypercomputation involve randomness, most research focuses on machines that can deterministically, or in a fixed way, solve these impossible problems. These ideas help scientists and mathematicians understand the limits of what computers can and cannot do, pushing the boundaries of what we think is possible in computing.
History
A computational model that goes beyond regular Turing machines was first introduced by Alan Turing in his 1938 PhD dissertation, titled Systems of Logic Based on Ordinals. In this work, Turing explored mathematical systems that include an oracle. An oracle is a special tool that can compute a single arbitrary function from naturals to naturals, which normal machines cannot do. Turing used this idea to show that even with these more powerful systems, some problems would still be impossible to solve, a concept known as undecidability. It's important to note that Turing's oracle machines are purely theoretical and cannot actually be built in the real world, as they are not physically realizable.
State space
Most functions cannot be computed by regular computers. There are countlessly many possible ways to go beyond what normal computers can do. This idea is part of studying hypercomputation, which looks at what could theoretically be computed if we had machines that could solve problems that normal computers cannot.
Models
Hypercomputers are imaginary machines that could solve problems beyond what regular computers can handle. These models range from useful but unrealistic ideas, like machines that can ask questions to an oracle, to more unusual concepts like random-function generators.
Some models suggest that if a system had special knowledge, like Chaitin's constant—a number that holds the solution to unsolved problems—it could solve many undecidable problems. Other ideas involve using physics in unusual ways, like harnessing real numbers or fuzzy logic, though these often require physics that we don’t fully understand. There are also ideas about machines that can complete infinite steps in finite time, inspired by ancient paradoxes, and theories involving quantum mechanics or systems that eventually find the right answer after many tries.
Analysis of capabilities
Many ideas about hypercomputation suggest new ways to use special tools, called oracles or advice functions, in regular machines. These tools could help solve problems that normal computers cannot. Some models, like supertasking Turing machines, could handle more complex tasks by reaching higher levels of the arithmetic hierarchy. Other models, such as limiting-recursion, focus on computing specific types of problems within the Turing degree.
| 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 is not possible in the real world. Martin Davis calls it "a myth" and says it is not a new idea. He points out that ideas about what can and cannot be computed have been studied for a long time.
Another person, Aran Nayebi, also thinks hypercomputation cannot work based on what we know about how the world operates.
This article is a child-friendly adaptation of the Wikipedia article on Hypercomputation, available under CC BY-SA 4.0.