Editing Hypercomputation (section)

==="Eventually correct" systems===
Some physically realizable systems will always eventually converge to the correct answer, but have the defect that they will often output an incorrect answer and stick with the incorrect answer for an uncomputably large period of time before eventually going back and correcting the mistake.

In mid 1960s, [[E Mark Gold]] and [[Hilary Putnam]] independently proposed models of [[inductive inference]] (the "limiting recursive functionals"<ref name=LimRecurs>{{cite journal | author=E. M. Gold | title=Limiting Recursion | journal=Journal of Symbolic Logic | volume=30 | issue=1 | pages=28–48 | year=1965 | jstor=2270580 | doi=10.2307/2270580| s2cid=33811657 }}, {{cite journal | author=E. Mark Gold | title=Language identification in the limit | journal=Information and Control | volume=10 | pages=447–474 | year=1967 | doi=10.1016/S0019-9958(67)91165-5 | issue=5| doi-access=free }}</ref> and "trial-and-error predicates",<ref name=TrialError>{{cite journal | author=Hilary Putnam | title=Trial and Error Predicates and the Solution to a Problem of Mostowksi | journal=Journal of Symbolic Logic | volume=30 | issue=1 | pages=49–57 | year=1965 | jstor=2270581 | doi=10.2307/2270581| s2cid=44655062 }}</ref> respectively). These models enable some nonrecursive sets of numbers or languages (including all [[recursively enumerable]] sets of languages) to be "learned in the limit"; whereas, by definition, only recursive sets of numbers or languages could be identified by a Turing machine. While the machine will stabilize to the correct answer on any learnable set in some finite time, it can only identify it as correct if it is recursive; otherwise, the correctness is established only by running the machine forever and noting that it never revises its answer. 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. (Note, however, that even if we have gotten to the correct answer (the end of the finite sequence) we are never ''sure'' that we have the correct answer.)"<ref name=TrialError/> [[L. K. Schubert]]'s 1974 paper "Iterated Limiting Recursion and the Program Minimization Problem"<ref name=IterLimRec>{{cite journal| author=L. K. Schubert | title=Iterated Limiting Recursion and the Program Minimization Problem | journal=Journal of the ACM | volume=21 | issue=3 |date=July 1974 | doi=10.1145/321832.321841| pages=436–445| s2cid=2071951 | doi-access=free }}</ref> studied the effects of iterating the limiting procedure; this allows any [[arithmetic hierarchy|arithmetic]] predicate to be computed. 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."

A symbol sequence is ''computable in the limit'' if there is a finite, possibly non-halting program on a [[universal Turing machine]] that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other [[computable real]], but still excludes all noncomputable reals. The 'Monotone Turing machines' traditionally used in [[minimum description length|description size]] theory cannot edit their previous outputs; generalized Turing machines, as defined by [[Jürgen Schmidhuber]], can. 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. Due to limitations first exhibited by [[Kurt Gödel]] (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the [[halting problem]] could be solved. Schmidhuber (<ref name=genTuring2000>{{cite arXiv | eprint=quant-ph/0011122| last1=Schmidhuber| first1=Juergen| title=Algorithmic Theories of Everything| year=2000}}</ref><ref name=GenKolm>{{cite journal| author=J. Schmidhuber | title=Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit | journal=International Journal of Foundations of Computer Science | volume=13 | issue=4 | pages=587–612 | year=2002 | url=http://www.idsia.ch/~juergen/kolmogorov.html| doi=10.1142/S0129054102001291 | arxiv=quant-ph/0011122 | bibcode=2000quant.ph.11122S}}</ref>) uses this approach to define the set of formally describable or constructively computable universes or constructive [[theory of everything|theories of everything]]. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a [[Specker sequence]].