Editing Hypercomputation (section)

==Models==
Hypercomputer models range from useful but probably unrealizable (such as Turing's original oracle machines), to less-useful random-function generators that are more plausibly "realizable" (such as a [[random Turing machine]]).

===Uncomputable inputs or black-box components===
{{prose|section|date=July 2023}}
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:

<!-- Please include only well-cited examples, we don't need to hear about a penguin whose eyeblinks encode Chaitin's constant -->
*Turing's original oracle machines, defined by Turing in 1939.
*A [[real computer]] (a sort of idealized [[analog computer]]) can perform hypercomputation<ref>[[Arnold Schönhage]], "On the power of random access machines", in ''Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP)'', pages 520–529, 1979.  Source of citation: [[Scott Aaronson]], "NP-complete Problems and Physical Reality"[http://www.scottaaronson.com/papers/npcomplete.pdf] p.&nbsp;12</ref> if physics admits general [[real number|real]] variables (not just [[computable number|computable reals]]), and these are in some way "harnessable" for useful (rather than random) computation.  This might require quite bizarre laws of physics (for example, a measurable [[physical constant]] with an oracular value, such as [[Chaitin's constant]]), and would require the ability to measure the real-valued physical value to arbitrary precision, though standard physics makes such arbitrary-precision measurements theoretically infeasible.<ref name=HodgesSCIAM>{{cite web |url=http://www.turing.org.uk/philosophy/sciam.html |title=The Professors and the Brainstorms |author=Andrew Hodges |access-date=23 September 2011 |work=The Alan Turing Home Page }}</ref>
**Similarly, a neural net that somehow had Chaitin's constant exactly embedded in its weight function would be able to solve the halting problem,<ref>{{cite journal |author1=H.T. Siegelmann |author2=E.D. Sontag | title=Analog Computation via Neural Networks | journal=Theoretical Computer Science | volume=131 |issue=2 | pages=331–360 | year=1994 |doi=10.1016/0304-3975(94)90178-3 | doi-access=free }}</ref> but is subject to the same physical difficulties as other models of hypercomputation based on real computation.
*Certain [[fuzzy logic]]-based "fuzzy Turing machines" can, by definition, accidentally solve the halting problem, but only because their ability to solve the halting problem is indirectly assumed in the specification of the machine; this tends to be viewed as a "bug" in the original specification of the machines.<ref>{{Cite journal|last=Biacino|first=L.|author2=Gerla, G.|year=2002|title=Fuzzy logic, continuity and effectiveness|journal=Archive for Mathematical Logic|issn=0933-5846|volume=41|issue=7|pages=643–667|doi=10.1007/s001530100128|citeseerx=10.1.1.2.8029|s2cid=12513452}}</ref><ref name=ClassicalFuzzy>{{Cite journal|last=Wiedermann|first=Jiří |year=2004|title=Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines|journal= Theoretical Computer Science|volume=317|issue=1–3|pages=61–69|doi=10.1016/j.tcs.2003.12.004|quote=Their (ability to solve the halting problem) is due to their acceptance criterion in which the ability to solve the halting problem is indirectly assumed.|doi-access=free}}</ref>
**Similarly, a proposed model known as [[fair nondeterminism]] can accidentally allow the oracular computation of noncomputable functions, because some such systems, by definition, have the oracular ability to identify and reject inputs that would "unfairly" cause a subsystem to run forever.<ref>{{cite journal|title=Nondeterminism, Fairness and a Fundamental Analogy|journal=EATCS Bulletin|volume=37|pages=186–193|year=1989|author1=Edith Spaan |author2=Leen Torenvliet |author3=Peter van Emde Boas }}</ref><ref>{{Cite journal|doi=10.1016/j.amc.2005.09.076|title=The many forms of hypercomputation|year=2006|last1=Ord|first1=Toby|journal=Applied Mathematics and Computation|volume=178|pages=143–153}}</ref>
*Dmytro Taranovsky has proposed a [[finitism|finitistic]] model of traditionally non-finitistic branches of analysis, built around a Turing machine equipped with a rapidly increasing function as its oracle. By this and more complicated models he was able to give an interpretation of second-order arithmetic. These models require an uncomputable input, such as a physical event-generating process where the interval between events grows at an uncomputably large rate.<ref name=Taranovsky>{{cite web | author=Dmytro Taranovsky | date=July 17, 2005 | title=Finitism and Hypercomputation | url=http://web.mit.edu/dmytro/www/FinitismPaper.htm | access-date=Apr 26, 2011}}</ref>
**Similarly, one unorthodox interpretation of a model of [[unbounded nondeterminism]] posits, by definition, that the length of time required for an "Actor" to settle is fundamentally unknowable, and therefore it cannot be proven, within the model, that it does not take an uncomputably long period of time.<ref>Hewitt, Carl. "What Is Commitment." Physical, Organizational, and Social (Revised), Coordination, Organizations, Institutions, and Norms in Agent Systems II: AAMAS (2006).</ref><!-- There is also an argument in Hewitt 2006 that this model is justified in the physical world, but this appears to be unbased [[WP:FRINGE]] speculation that I can't find anyone else endorsing or even explicitly acknowledging. -->

==="Infinite computational steps" models===
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]]. Simply being able to run for an unbounded number of steps does not suffice. One mathematical model is the [[Zeno machine]] (inspired by [[Zeno's paradox]]). The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc.  By summing [[1/2 + 1/4 + 1/8 + 1/16 + ⋯|1&nbsp;+&nbsp;½&nbsp;+&nbsp;¼&nbsp;+&nbsp;...]] (a [[geometric series]]) we see that the machine performs infinitely many steps in a total of 2 minutes. According to [[Oron Shagrir]], Zeno machines introduce physical paradoxes and its state is logically undefined outside of one-side open period of [0, 2), thus undefined exactly at 2 minutes after beginning of the computation.<ref>These models have been independently developed by many different authors, including {{cite book|author=Hermann Weyl|  year=1927 | title=Philosophie der Mathematik und Naturwissenschaft| author-link=Hermann Weyl }}; the model is discussed in {{cite journal
 |author=[[Oron Shagrir|Shagrir, O.]]
 |title=Super-tasks, accelerating Turing machines and uncomputability 
 |journal= Theoretical Computer Science
 |date=June 2004 
 |pages=105–114 
 |doi=10.1016/j.tcs.2003.12.007 
 |volume=317 
 |issue=1–3 
 |doi-access=free 
 }}, {{cite journal| author=Petrus H. Potgieter| title=Zeno machines and hypercomputation| journal=Theoretical Computer Science| volume=358 | issue=1 |date=July 2006 | pages=23–33| doi=10.1016/j.tcs.2005.11.040| arxiv=cs/0412022| s2cid=6749770}} and {{cite journal
 |author=Vincent C. Müller 
 |title=On the possibilities of hypercomputing supertasks 
 |journal=Minds and Machines 
 |volume=21 
 |issue=1 
 |date=2011 
 |pages=83–96 
 |url=http://philpapers.org/rec/MLLOTP
 |doi=10.1007/s11023-011-9222-6
|citeseerx=10.1.1.225.3696 
 |s2cid=253434 
 }}</ref>

It seems natural that the possibility of time travel (existence of [[closed timelike curve]]s (CTCs)) makes hypercomputation possible by itself. However, this is not so since a CTC does not provide (by itself) the unbounded amount of storage that an infinite computation would require. Nevertheless, there are spacetimes in which the CTC region can be used for relativistic hypercomputation.<ref>{{Cite journal|arxiv = 1105.0047|doi = 10.1142/S0129626412400105|title = Closed Timelike Curves in Relativistic Computation|year = 2012|last1 = Andréka|first1 = Hajnal|last2 = Németi|first2 = István|last3 = Székely|first3 = Gergely|journal = Parallel Processing Letters|volume = 22|issue = 3|s2cid = 16816151}}</ref> According to a 1992 paper,<ref>{{Cite journal|doi = 10.1007/BF00682813|title = Does general relativity allow an observer to view an eternity in a finite time?|year = 1992|last1 = Hogarth|first1 = Mark L.|journal = Foundations of Physics Letters|volume = 5|issue = 2|pages = 173–181|bibcode = 1992FoPhL...5..173H|s2cid = 120917288}}</ref> a computer operating in a [[Malament–Hogarth spacetime]] or in orbit around a rotating [[black hole]]<ref>{{cite book | chapter=Can General Relativistic Computers Break the Turing Barrier? | author=István Neméti | author2=Hajnal Andréka | author2-link=Hajnal Andréka | title=Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings | publisher=Springer | series=Lecture Notes in Computer Science | volume=3988 | doi=10.1007/11780342 | year=2006 | isbn=978-3-540-35466-6 | url-access=registration | url=https://archive.org/details/logicalapproache0000conf }}</ref> could theoretically perform non-Turing computations for an observer inside the black hole.<ref>{{Cite journal|arxiv = gr-qc/0104023|last1 = Etesi|first1 = Gabor|last2 = Nemeti|first2 = Istvan|title = Non-Turing computations via Malament-Hogarth space-times|journal = International Journal of Theoretical Physics|year = 2002|volume = 41|issue = 2|pages = 341–370|doi = 10.1023/A:1014019225365|s2cid = 17081866}}</ref><ref>{{Cite journal|doi = 10.1086/289716|title = Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes|year = 1993|last1 = Earman|first1 = John|last2 = Norton|first2 = John D.|journal = Philosophy of Science|volume = 60|pages = 22–42|s2cid = 122764068}}</ref> 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.<ref>{{Cite journal|arxiv = gr-qc/0209061|last1 = Brun|first1 = Todd A.|title = Computers with closed timelike curves can solve hard problems|journal = Found. Phys. Lett.|year = 2003|volume = 16|issue = 3|pages = 245–253|doi = 10.1023/A:1025967225931|s2cid = 16136314}}</ref><ref>[[Scott Aaronson|S. Aaronson]] and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [http://scottaaronson.com/papers/ctc.pdf]</ref>

===Quantum models===
Some scholars conjecture that a [[Quantum mechanics|quantum mechanical]] system which somehow uses an infinite superposition of states could compute a non-[[computable function]].<ref>There have been some claims to this effect; see {{cite journal | author = Tien Kieu | title = Quantum Algorithm for the Hilbert's Tenth Problem | journal = Int. J. Theor. Phys. | year = 2003 | volume = 42 | arxiv = quant-ph/0110136 | pages = 1461–1478 | doi = 10.1023/A:1025780028846 | issue = 7| title-link = Hilbert problems | s2cid = 6634980 }} or {{cite journal | author = M. Ziegler | title = Computational Power of Infinite Quantum Parallelism | year = 2005 | journal = [[International Journal of Theoretical Physics]] | volume = 44 | issue = 11 | pages = 2059–2071 | doi = 10.1007/s10773-005-8984-0| arxiv = quant-ph/0410141 | bibcode = 2005IJTP...44.2059Z | s2cid = 9879859 }} and the ensuing literature. For a retort see  {{cite journal | author = Warren D. Smith | doi = 10.1016/j.amc.2005.09.078 | title = Three counterexamples refuting Kieu's plan for "quantum adiabatic hypercomputation"; and some uncomputable quantum mechanical tasks | journal = Applied Mathematics and Computation | volume = 178 | issue = 1 | pages = 184–193| year = 2006 }}.
</ref> This is not possible using the standard [[qubit]]-model [[quantum computer]], because it is proven that a regular quantum computer is [[PSPACE]]-[[Reduction (complexity)|reducible]] (a quantum computer running in [[polynomial time]] can be simulated by a classical computer running in [[polynomial space]]).<ref>{{cite journal |url=http://www.cs.berkeley.edu/~vazirani/bv.ps |doi=10.1137/S0097539796300921|title=Quantum Complexity Theory|year=1997|last1=Bernstein|first1=Ethan|last2=Vazirani|first2=Umesh|journal=SIAM Journal on Computing|volume=26|issue=5|pages=1411–1473}}</ref>

==="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]].