For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.
A system granted knowledge of the uncomputable, oracular Chaitin's constant (a number with an infinite sequence of digits that encode the solution to the halting problem) as an input can solve a large number of useful undecidable problems; a system granted an uncomputable random-number generator as an input can create random uncomputable functions, but is generally not believed to be able to meaningfully solve "useful" uncomputable functions such as the halting problem.
There are an unlimited number of different types of conceivable hypercomputers, including: In order to work correctly, certain computations by the machines below literally require infinite, rather than merely unlimited but finite, physical space and resources; in contrast, with a Turing machine, any given computation that halts will require only finite physical space and resources.
A Turing machine that can complete infinitely many steps in finite time, a feat known as a supertask.
By summing 1 + ½ + ¼ + ... (a geometric series) we see that the machine performs infinitely many steps in a total of 2 minutes.
However, this is not so since a CTC does not provide (by itself) the unbounded amount of storage that an infinite computation would require.
[17][18] Access to a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which, while Turing-decidable, is generally considered computationally intractable.
[19][20] Some scholars conjecture that a quantum mechanical system which somehow uses an infinite superposition of states could compute a non-computable function.
In mid 1960s, E Mark Gold and Hilary Putnam independently proposed models of inductive inference (the "limiting recursive functionals"[23] and "trial-and-error predicates",[24] respectively).
Putnam identified this new interpretation as the class of "empirical" predicates, stating: "if we always 'posit' that the most recently generated answer is correct, we will make a finite number of mistakes, but we will eventually get the correct answer.
Schubert wrote, "Intuitively, iterated limiting identification might be regarded as higher-order inductive inference performed collectively by an ever-growing community of lower order inductive inference machines."
He defines the constructively describable symbol sequences as those that have a finite, non-halting program running on a generalized Turing machine, such that any output symbol eventually converges; that is, it does not change any more after some finite initial time interval.
Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a Specker sequence.
Many hypercomputation proposals amount to alternative ways to read an oracle or advice function embedded into an otherwise classical machine.
For example, supertasking Turing machines, under the usual assumptions, would be able to compute any predicate in the truth-table degree containing