457:
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
260:(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:
380:(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. According to a 1992 paper, a computer operating in a
211:
493:, 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
321:
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
456:
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
341:
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.
1133:, in his writings on hypercomputation, refers to this subject as "a myth" and offers counter-arguments to the physical realizability of hypercomputation. As for its theory, he argues against the claims that this is a new field founded in the 1990s. This point of view relies on the history of
1210:"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper
436:
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.
304:-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.
294:
Similarly, a neural net that somehow had
Chaitin's constant exactly embedded in its weight function would be able to solve the halting problem, but is subject to the same physical difficulties as other models of hypercomputation based on real
469:
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."
2981:
751:
311:
can accidentally allow the oracular computation of noncomputable functions, because some such systems, by definition, have the oracular ability to identify reject inputs that would "unfairly" cause a subsystem to run
64:
states that any "computable" function that can be computed by a mathematician with a pen and paper using a finite set of simple algorithms, can be computed by a Turing machine. Hypercomputers compute functions that a
329:
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
193:
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
2801:
373:, 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.
1137:(degrees of unsolvability, computability over functions, real numbers and ordinals), as also mentioned above. In his argument, he makes a remark that all of hypercomputation is little more than: "
291:), 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.
1035:
3004:
846:
1081:
934:
794:
663:
631:
563:
183:
1528:
Hewitt, Carl. "What Is
Commitment." Physical, Organizational, and Social (Revised), Coordination, Organizations, Institutions, and Norms in Agent Systems II: AAMAS (2006).
1115:
595:
144:
452:(the "limiting recursive functionals" and "trial-and-error predicates", respectively). These models enable some nonrecursive sets of numbers or languages (including all
2395:
283:), 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
974:
2025:
Warren D. Smith (2006). "Three counterexamples refuting Kieu's plan for "quantum adiabatic hypercomputation"; and some uncomputable quantum mechanical tasks".
1979:
2832:
1446:
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.
465:'s 1974 paper "Iterated Limiting Recursion and the Program Minimization Problem" studied the effects of iterating the limiting procedure; this allows any
361:). 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
1762:
Logical
Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings
501:
could be solved. Schmidhuber () uses this approach to define the set of formally describable or constructively computable universes or constructive
690:
2879:
Ord, Toby (2002). "Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation".
3024:
2379:
1779:
388:
could theoretically perform non-Turing computations for an observer inside the black hole. Access to a CTC may allow the rapid solution to
362:
94:
2732:
2704:
2552:"Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems"
856:
2369:
874:
381:
3048:
2649:
1130:
529:. For example, supertasking Turing machines, under the usual assumptions, would be able to compute any predicate in the
990:
481:
that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other
505:. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a
486:
1840:
Earman, John; Norton, John D. (1993). "Forever is a Day: Supertasks in
Pitowsky and Malament-Hogarth Spacetimes".
3043:
2269:"Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit"
880:
392:
problems, a complexity class which, while Turing-decidable, is generally considered computationally intractable.
1666:
Andréka, Hajnal; Németi, István; Székely, Gergely (2012). "Closed
Timelike Curves in Relativistic Computation".
1458:
Edith Spaan; Leen
Torenvliet; Peter van Emde Boas (1989). "Nondeterminism, Fairness and a Fundamental Analogy".
61:
478:
326:
322:
as a physical event-generating process where the interval between events grows at an uncomputably large rate.
110:
is still present. Turing's oracle machines are mathematical abstractions, and are not physically realizable.
1711:
Hogarth, Mark L. (1992). "Does general relativity allow an observer to view an eternity in a finite time?".
353:. Simply being able to run for an unbounded number of steps does not suffice. One mathematical model is the
2714:
Cockshott, P.; Michaelson, G. (2007). "Are there new Models of
Computation? Reply to Wegner and Eberbach".
2770:
1630:
1375:
1240:
453:
1155:
530:
497:(1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the
377:
194:
73:
813:
490:
288:
257:
417:
2465:
2290:
1998:
1720:
1134:
1054:
898:
767:
636:
604:
536:
526:
502:
466:
154:
50:
38:
2916:
Sharma, Ashish (2022). "Nature
Inspired Algorithms with Randomized Hypercomputational Perspective".
1635:
1245:
462:
2894:
2775:
1424:"Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines"
1283:
1040:
633:. Gold further showed that limiting partial recursion would allow the computation of precisely the
522:
485:, but still excludes all noncomputable reals. The 'Monotone Turing machines' traditionally used in
449:
405:
308:
107:
2742:. New York, Boston, Dordrecht, London, Moscow: Plenum Publishers. pp. 137–160. Archived from
1380:
1088:
568:
2968:
2933:
2898:
2880:
2867:
2824:
2788:
2489:
2421:
2389:
2343:
2325:
2280:
2247:
2228:
2184:
2176:
2112:
2104:
2014:
1988:
1966:
1948:
1902:
1884:
1857:
1822:
1804:
1795:
Etesi, Gabor; Nemeti, Istvan (2002). "Non-Turing computations via
Malament-Hogarth space-times".
1736:
1693:
1675:
1648:
1606:
1588:
1401:
1266:
122:
2547:
2409:
2450:
2159:
Hilary Putnam (1965). "Trial and Error
Predicates and the Solution to a Problem of Mostowksi".
369:) we see that the machine performs infinitely many steps in a total of 2 minutes. According to
3020:
2700:
2481:
2375:
1775:
1755:
1393:
1258:
597:. Limiting-recursion, by contrast, can compute any predicate or function in the corresponding
525:
embedded into an otherwise classical machine. Others allow access to some higher level of the
401:
358:
284:
280:
42:
1225:
2996:
2958:
2925:
2859:
2816:
2780:
2719:
2592:
2563:
2527:
2473:
2431:
2335:
2298:
2218:
2168:
2136:
2096:
2066:
2034:
2006:
1958:
1936:
1894:
1849:
1814:
1767:
1728:
1685:
1640:
1598:
1566:
1486:
1435:
1385:
1346:
1250:
1191:
1183:
506:
425:
413:
366:
54:
2844:
2507:
1150:
864:
498:
482:
421:
389:
272:
46:
2743:
2625:
Martin Davis (Jan 2003). "The Myth of Hypercomputation". In Alexandra Shlapentokh (ed.).
953:
2469:
2294:
2002:
1724:
2511:
1922:
and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent
1919:
1875:
Brun, Todd A. (2003). "Computers with closed timelike curves can solve hard problems".
1760:
1291:
518:
103:
99:
66:
2626:
2141:
2124:
489:
theory cannot edit their previous outputs; generalized Turing machines, as defined by
3037:
2937:
2828:
2532:
2515:
2365:
1861:
1740:
1351:
1334:
1295:
1196:
598:
494:
445:
268:
2634:. MFO Report. Vol. 3. Mathematisches Forschungsinstitut Oberwolfach. p. 2.
2628:
Miniworkshop: Hilbert's Tenth Problem, Mazur's Conjecture and Divisibility Sequences
2493:
2188:
2116:
1906:
1826:
1697:
1537:
These models have been independently developed by many different authors, including
1405:
106:
to naturals. He used this device to prove that even in those more powerful systems,
102:
was available, which could compute a single arbitrary (non-recursive) function from
2972:
2871:
2792:
2347:
2232:
2018:
1970:
1610:
1550:
1539:
1270:
1139:
if non-computable inputs are permitted, then non-computable outputs are attainable.
370:
354:
236:
2664:
1652:
1508:
404:
system which somehow uses an infinite superposition of states could compute a non-
2477:
1308:
2361:
441:
301:
276:
148:
89:
77:
76:
is uncomputable; however, most hypercomputing literature focuses instead on the
2268:
1187:
3000:
2929:
2820:
2784:
2596:
2568:
2551:
2339:
2302:
2070:
2038:
2010:
1962:
1898:
1818:
1689:
1644:
1602:
1571:
1554:
1490:
1440:
1423:
385:
2583:
Davis, Martin (2006). "Why there is no such discipline as hypercomputation".
2054:
1397:
2723:
1366:
Biacino, L.; Gerla, G. (2002). "Fuzzy logic, continuity and effectiveness".
941:
is an advice function giving connection weights; size is bounded by runtime
746:{\displaystyle \operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)}
350:
225:
17:
2485:
1262:
2435:
2223:
2206:
1977:
M. Ziegler (2005). "Computational Power of Infinite Quantum Parallelism".
1923:
1389:
2285:
2252:
1993:
1953:
1254:
318:
221:
1758:(2006). "Can General Relativistic Computers Break the Turing Barrier?".
69:
cannot and which are, hence, not computable in the Church–Turing sense.
2963:
2946:
2316:
Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation".
2180:
2108:
1732:
1579:
Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation".
119:
2426:
1889:
1809:
1288:
Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP)
517:
Many hypercomputation proposals amount to alternative ways to read an
2947:"X-machines and the halting problem: Building a super-Turing machine"
2885:
1771:
88:
A computational model going beyond Turing machines was introduced by
2412:(2008). "The extent of computation in Malament-Hogarth spacetimes".
2172:
2100:
2863:
2761:
Cooper, S. B. (2006). "Definability as hypercomputational effect".
2330:
2246:
Schmidhuber, Juergen (2000). "Algorithmic Theories of Everything".
1853:
1618:
1593:
376:
It seems natural that the possibility of time travel (existence of
2207:"Iterated Limiting Recursion and the Program Minimization Problem"
1680:
1226:"The Computational Power of Interactive Recurrent Neural Networks"
409:
1766:. Lecture Notes in Computer Science. Vol. 3988. Springer.
1555:"Super-tasks, accelerating Turing machines and uncomputability"
204:
80:
of deterministic, rather than random, uncomputable functions.
1174:
Turing, A. M. (1939). "Systems of Logic Based on Ordinals†".
264:
Turing's original oracle machines, defined by Turing in 1939.
3017:
Hypercomputation: Computing Beyond the Church–Turing Barrier
98:. This paper investigated mathematical systems in which an
416:, because it is proven that a regular quantum computer is
275:) can perform hypercomputation if physics admits general
256:
A system granted knowledge of the uncomputable, oracular
2273:
International Journal of Foundations of Computer Science
1477:
Ord, Toby (2006). "The many forms of hypercomputation".
477:
if there is a finite, possibly non-halting program on a
349:
infinitely many steps in finite time, a feat known as a
325:
Similarly, one unorthodox interpretation of a model of
232:
118:
In a sense, most functions are uncomputable: there are
2610:
Davis, Martin (2004). "The Myth of Hypercomputation".
49:
would be a hypercomputer; so too would one that could
1091:
1057:
993:
956:
901:
816:
770:
693:
639:
607:
571:
539:
157:
125:
2740:
Computability and Models: Perspectives East and West
424:
can be simulated by a classical computer running in
2682:Burgin, M. S. (1983). "Inductive Turing Machines".
1937:"Quantum Algorithm for the Hilbert's Tenth Problem"
1619:"On the possibilities of hypercomputing supertasks"
1759:
1109:
1075:
1029:
968:
928:
840:
788:
745:
657:
625:
589:
557:
177:
138:
2845:"Quantum Hypercomputation—Hype or Computation?*"
1933:There have been some claims to this effect; see
1544:Philosophie der Mathematik und Naturwissenschaft
1417:
1415:
1030:{\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}
2612:Alan Turing: Life and Legacy of a Great Thinker
1286:, "On the power of random access machines", in
2684:Notices of the Academy of Sciences of the USSR
2023:and the ensuing literature. For a retort see
1176:Proceedings of the London Mathematical Society
45:. For example, a machine that could solve the
2738:. In Cooper, S. B.; Goncharov, S. S. (eds.).
2414:British Journal for the Philosophy of Science
2200:
2198:
2154:
2152:
1502:
1500:
1294:, "NP-complete Problems and Physical Reality"
363:1 + ½ + ¼ + ...
8:
2699:. Monographs in computer science. Springer.
2394:: CS1 maint: multiple names: authors list (
2082:
2080:
1980:International Journal of Theoretical Physics
1797:International Journal of Theoretical Physics
1290:, pages 520–529, 1979. Source of citation:
2650:"Advances in Three Hypercomputation Models"
201:Uncomputable inputs or black-box components
2053:Bernstein, Ethan; Vazirani, Umesh (1997).
667:
408:. This is not possible using the standard
2962:
2884:
2774:
2657:Electronic Journal of Theoretical Physics
2567:
2531:
2425:
2329:
2284:
2251:
2222:
2140:
2087:E. M. Gold (1965). "Limiting Recursion".
1992:
1952:
1888:
1808:
1679:
1634:
1592:
1570:
1439:
1379:
1350:
1244:
1195:
1101:
1096:
1090:
1067:
1062:
1056:
1021:
1016:
1003:
998:
992:
955:
911:
906:
900:
832:
821:
815:
780:
775:
769:
732:
727:
714:
709:
692:
649:
644:
638:
617:
612:
606:
581:
576:
570:
549:
544:
538:
167:
162:
156:
130:
124:
2516:"Analog Computation via Neural Networks"
1335:"Analog Computation via Neural Networks"
1224:J. Cabessa; H.T. Siegelmann (Apr 2012).
1166:
147:computable functions, but there are an
2387:
2125:"Language identification in the limit"
185:) of possible super-Turing functions.
41:that can provide outputs that are not
2731:Cooper, S. B.; Odifreddi, P. (2003).
2451:"Computation Beyond the Turing Limit"
1333:H.T. Siegelmann; E.D. Sontag (1994).
337:"Infinite computational steps" models
307:Similarly, a proposed model known as
7:
1309:"The Professors and the Brainstorms"
2989:Applied Mathematics and Computation
2903:Stanford Encyclopedia of Philosophy
2763:Applied Mathematics and Computation
2585:Applied Mathematics and Computation
2364:, Felipe Cucker, Michael Shub, and
2027:Applied Mathematics and Computation
1507:Dmytro Taranovsky (July 17, 2005).
1479:Applied Mathematics and Computation
461:that we have the correct answer.)"
1212:Systems of Logic Based On Ordinals
1093:
1059:
1013:
995:
978:Arithmetical Quasi-Inductive sets
903:
818:
772:
724:
706:
641:
609:
573:
541:
164:
127:
95:Systems of Logic Based on Ordinals
51:correctly evaluate every statement
25:
2899:"Computation in Physical Systems"
886:dependent on spacetime structure
841:{\displaystyle \Delta _{k+1}^{0}}
448:independently proposed models of
317:Dmytro Taranovsky has proposed a
893:analog recurrent neural network
400:Some scholars conjecture that a
287:with an oracular value, such as
209:
2982:"The case for hypercomputation"
2843:Hagar, A.; Korolev, A. (2007).
2371:Complexity and Real Computation
1509:"Finitism and Hypercomputation"
1076:{\displaystyle \Delta _{1}^{1}}
985:classical fuzzy Turing machine
929:{\displaystyle \Delta _{1}^{0}}
789:{\displaystyle \Delta _{2}^{0}}
658:{\displaystyle \Sigma _{2}^{0}}
626:{\displaystyle \Delta _{2}^{0}}
558:{\displaystyle \Sigma _{1}^{0}}
420:(a quantum computer running in
178:{\displaystyle 2^{\aleph _{0}}}
3015:Syropoulos, Apostolos (2008).
1713:Foundations of Physics Letters
1368:Archive for Mathematical Logic
923:
917:
863:incomparable with traditional
755:dependent on outside observer
384:or in orbit around a rotating
224:format but may read better as
1:
2663:(36): 169–182. Archived from
2142:10.1016/S0019-9958(67)91165-5
948:infinite time Turing machine
92:in his 1938 PhD dissertation
72:Technically, the output of a
2648:Aoun, Mario Antoine (2016).
2556:Theoretical Computer Science
2533:10.1016/0304-3975(94)90178-3
2520:Theoretical Computer Science
2478:10.1126/science.268.5210.545
2449:H.T. Siegelmann (Apr 1995).
2318:Theoretical Computer Science
2205:L. K. Schubert (July 1974).
1581:Theoretical Computer Science
1559:Theoretical Computer Science
1548:; the model is discussed in
1428:Theoretical Computer Science
1352:10.1016/0304-3975(94)90178-3
1339:Theoretical Computer Science
1110:{\displaystyle \Pi _{1}^{1}}
1085:for the one-sequence model;
590:{\displaystyle \Pi _{1}^{0}}
432:"Eventually correct" systems
2951:Formal Aspects of Computing
2733:"Incomputability in Nature"
2055:"Quantum Complexity Theory"
1668:Parallel Processing Letters
1049:increasing function oracle
139:{\displaystyle \aleph _{0}}
3065:
2697:Super-recursive algorithms
1617:Vincent C. MĂĽller (2011).
875:Malament–Hogarth spacetime
382:Malament–Hogarth spacetime
345:A Turing machine that can
3001:10.1016/j.amc.2005.09.067
2930:10.1016/j.ins.2022.05.020
2785:10.1016/j.amc.2005.09.072
2597:10.1016/j.amc.2005.09.066
2569:10.1016/j.tcs.2008.09.050
2340:10.1016/j.tcs.2005.11.040
2303:10.1142/S0129054102001291
2161:Journal of Symbolic Logic
2089:Journal of Symbolic Logic
2071:10.1137/S0097539796300921
2059:SIAM Journal on Computing
2039:10.1016/j.amc.2005.09.078
2011:10.1007/s10773-005-8984-0
1690:10.1142/S0129626412400105
1645:10.1007/s11023-011-9222-6
1603:10.1016/j.tcs.2005.11.040
1572:10.1016/j.tcs.2003.12.007
1491:10.1016/j.amc.2005.09.076
1441:10.1016/j.tcs.2003.12.004
1422:Wiedermann, Jiřà (2004).
1313:The Alan Turing Home Page
1197:21.11116/0000-0001-91CE-3
762:limiting/trial-and-error
37:is a set of hypothetical
1188:10.1112/plms/s2-45.1.161
513:Analysis of capabilities
479:universal Turing machine
327:unbounded nondeterminism
35:super-Turing computation
2980:Stannett, Mike (2006).
2945:Stannett, Mike (1990).
2821:10.1023/A:1021105915386
2267:J. Schmidhuber (2002).
2129:Information and Control
1963:10.1023/A:1025780028846
1899:10.1023/A:1025967225931
1819:10.1023/A:1014019225365
857:Blum–Shub–Smale machine
601:, which is known to be
475:computable in the limit
233:converting this section
1111:
1077:
1031:
970:
930:
842:
790:
747:
674:Computable predicates
659:
627:
591:
559:
503:theories of everything
454:recursively enumerable
378:closed timelike curves
179:
140:
3049:Theory of computation
2852:Philosophy of Science
2800:Copeland, J. (2002).
2724:10.1093/comjnl/bxl062
2695:Burgin, Mark (2005).
2224:10.1145/321832.321841
2123:E. Mark Gold (1967).
1842:Philosophy of Science
1390:10.1007/s001530100128
1156:Limits of computation
1112:
1078:
1032:
971:
931:
843:
791:
748:
660:
628:
592:
560:
473:A symbol sequence is
271:(a sort of idealized
195:random Turing machine
180:
141:
74:random Turing machine
39:models of computation
27:Models of computation
2918:Information Sciences
2895:Piccinini, Gualtiero
2716:The Computer Journal
1255:10.1162/neco_a_00263
1135:computability theory
1089:
1055:
991:
954:
899:
814:
768:
691:
637:
605:
569:
537:
527:arithmetic hierarchy
279:variables (not just
155:
123:
62:Church–Turing thesis
2470:1995Sci...268..545S
2436:10.1093/bjps/axn031
2295:2000quant.ph.11122S
2003:2005IJTP...44.2059Z
1941:Int. J. Theor. Phys
1725:1992FoPhL...5..173H
1106:
1072:
1039:for any computable
1026:
1008:
969:{\displaystyle AQI}
916:
837:
804:iterated limiting (
785:
737:
719:
654:
622:
586:
554:
450:inductive inference
406:computable function
309:fair nondeterminism
2964:10.1007/BF01888233
2809:Minds and Machines
2802:"Hypercomputation"
2211:Journal of the ACM
1935:Tien Kieu (2003).
1733:10.1007/BF00682813
1623:Minds and Machines
1233:Neural Computation
1107:
1092:
1073:
1058:
1027:
1012:
994:
966:
926:
902:
838:
817:
786:
771:
743:
723:
705:
655:
640:
623:
608:
587:
572:
555:
540:
531:truth-table degree
491:JĂĽrgen Schmidhuber
402:quantum mechanical
289:Chaitin's constant
258:Chaitin's constant
235:, if appropriate.
175:
136:
3026:978-0-387-30886-9
2897:(June 16, 2021).
2464:(5210): 545–548.
2381:978-0-387-98281-6
1987:(11): 2059–2071.
1877:Found. Phys. Lett
1781:978-3-540-35466-6
1123:
1122:
285:physical constant
254:
253:
43:Turing-computable
16:(Redirected from
3056:
3044:Hypercomputation
3030:
3011:
3009:
3003:. Archived from
2986:
2976:
2966:
2941:
2912:
2910:
2909:
2890:
2888:
2875:
2849:
2839:
2837:
2831:. Archived from
2806:
2796:
2778:
2757:
2755:
2754:
2748:
2737:
2727:
2710:
2691:
2678:
2676:
2675:
2669:
2654:
2636:
2635:
2633:
2622:
2616:
2615:
2607:
2601:
2600:
2580:
2574:
2573:
2571:
2562:(4–5): 426–442.
2544:
2538:
2537:
2535:
2504:
2498:
2497:
2455:
2446:
2440:
2439:
2429:
2406:
2400:
2399:
2393:
2385:
2358:
2352:
2351:
2333:
2313:
2307:
2306:
2288:
2286:quant-ph/0011122
2264:
2258:
2257:
2255:
2253:quant-ph/0011122
2243:
2237:
2236:
2226:
2202:
2193:
2192:
2156:
2147:
2146:
2144:
2120:
2084:
2075:
2074:
2065:(5): 1411–1473.
2050:
2044:
2042:
2022:
1996:
1994:quant-ph/0410141
1974:
1956:
1954:quant-ph/0110136
1947:(7): 1461–1478.
1931:
1925:
1917:
1911:
1910:
1892:
1872:
1866:
1865:
1837:
1831:
1830:
1812:
1792:
1786:
1785:
1772:10.1007/11780342
1765:
1751:
1745:
1744:
1708:
1702:
1701:
1683:
1663:
1657:
1656:
1638:
1614:
1596:
1576:
1574:
1565:(1–3): 105–114.
1547:
1535:
1529:
1526:
1520:
1519:
1517:
1515:
1504:
1495:
1494:
1474:
1468:
1467:
1455:
1449:
1448:
1443:
1419:
1410:
1409:
1383:
1363:
1357:
1356:
1354:
1330:
1324:
1323:
1321:
1319:
1304:
1298:
1284:Arnold Schönhage
1281:
1275:
1274:
1248:
1230:
1221:
1215:
1208:
1202:
1201:
1199:
1171:
1116:
1114:
1113:
1108:
1105:
1100:
1082:
1080:
1079:
1074:
1071:
1066:
1036:
1034:
1033:
1028:
1025:
1020:
1007:
1002:
975:
973:
972:
967:
935:
933:
932:
927:
915:
910:
847:
845:
844:
839:
836:
831:
795:
793:
792:
787:
784:
779:
752:
750:
749:
744:
742:
738:
736:
731:
718:
713:
668:
664:
662:
661:
656:
653:
648:
632:
630:
629:
624:
621:
616:
596:
594:
593:
588:
585:
580:
564:
562:
561:
556:
553:
548:
507:Specker sequence
487:description size
426:polynomial space
418:PSPACE-reducible
414:quantum computer
367:geometric series
281:computable reals
249:
246:
240:
231:You can help by
213:
212:
205:
184:
182:
181:
176:
174:
173:
172:
171:
145:
143:
142:
137:
135:
134:
55:Peano arithmetic
31:Hypercomputation
21:
3064:
3063:
3059:
3058:
3057:
3055:
3054:
3053:
3034:
3033:
3027:
3014:
3007:
2984:
2979:
2944:
2915:
2907:
2905:
2893:
2878:
2847:
2842:
2835:
2804:
2799:
2760:
2752:
2750:
2746:
2735:
2730:
2713:
2707:
2694:
2690:(6): 1289–1293.
2681:
2673:
2671:
2667:
2652:
2647:
2644:
2642:Further reading
2639:
2631:
2624:
2623:
2619:
2609:
2608:
2604:
2582:
2581:
2577:
2546:
2545:
2541:
2508:Hava Siegelmann
2506:
2505:
2501:
2453:
2448:
2447:
2443:
2408:
2407:
2403:
2386:
2382:
2360:
2359:
2355:
2315:
2314:
2310:
2266:
2265:
2261:
2245:
2244:
2240:
2204:
2203:
2196:
2173:10.2307/2270581
2158:
2157:
2150:
2122:
2101:10.2307/2270580
2086:
2085:
2078:
2052:
2051:
2047:
2024:
1976:
1934:
1932:
1928:
1918:
1914:
1874:
1873:
1869:
1839:
1838:
1834:
1794:
1793:
1789:
1782:
1754:István Neméti;
1753:
1752:
1748:
1710:
1709:
1705:
1665:
1664:
1660:
1636:10.1.1.225.3696
1616:
1578:
1549:
1538:
1536:
1532:
1527:
1523:
1513:
1511:
1506:
1505:
1498:
1476:
1475:
1471:
1457:
1456:
1452:
1421:
1420:
1413:
1365:
1364:
1360:
1332:
1331:
1327:
1317:
1315:
1307:Andrew Hodges.
1306:
1305:
1301:
1282:
1278:
1246:10.1.1.411.7540
1239:(4): 996–1019.
1228:
1223:
1222:
1218:
1209:
1205:
1173:
1172:
1168:
1164:
1151:Digital physics
1147:
1128:
1087:
1086:
1053:
1052:
989:
988:
952:
951:
897:
896:
865:computable real
812:
811:
766:
765:
704:
700:
689:
688:
635:
634:
603:
602:
567:
566:
535:
534:
523:advice function
515:
499:halting problem
483:computable real
434:
422:polynomial time
398:
390:PSPACE-complete
339:
273:analog computer
250:
244:
241:
230:
214:
210:
203:
191:
163:
158:
153:
152:
126:
121:
120:
116:
86:
47:halting problem
28:
23:
22:
15:
12:
11:
5:
3062:
3060:
3052:
3051:
3046:
3036:
3035:
3032:
3031:
3025:
3012:
3010:on 2016-03-04.
2977:
2957:(1): 331–341.
2942:
2913:
2891:
2876:
2864:10.1086/521969
2858:(3): 347–363.
2840:
2838:on 2016-03-14.
2815:(4): 461–502.
2797:
2776:10.1.1.65.4088
2758:
2728:
2711:
2705:
2692:
2679:
2643:
2640:
2638:
2637:
2617:
2602:
2575:
2539:
2526:(2): 331–360.
2512:Eduardo Sontag
2499:
2441:
2420:(4): 659–674.
2401:
2380:
2353:
2308:
2279:(4): 587–612.
2259:
2238:
2217:(3): 436–445.
2194:
2148:
2135:(5): 447–474.
2076:
2045:
2033:(1): 184–193.
1926:
1912:
1883:(3): 245–253.
1867:
1854:10.1086/289716
1832:
1803:(2): 341–370.
1787:
1780:
1756:Hajnal Andréka
1746:
1719:(2): 173–181.
1703:
1658:
1530:
1521:
1496:
1469:
1460:EATCS Bulletin
1450:
1434:(1–3): 61–69.
1411:
1374:(7): 643–667.
1358:
1345:(2): 331–360.
1325:
1299:
1292:Scott Aaronson
1276:
1216:
1203:
1165:
1163:
1160:
1159:
1158:
1153:
1146:
1143:
1127:
1124:
1121:
1120:
1118:
1104:
1099:
1095:
1083:
1070:
1065:
1061:
1050:
1046:
1045:
1043:
1037:
1024:
1019:
1015:
1011:
1006:
1001:
997:
986:
982:
981:
979:
976:
965:
962:
959:
949:
945:
944:
942:
936:
925:
922:
919:
914:
909:
905:
894:
890:
889:
887:
884:
877:
871:
870:
868:
861:
859:
853:
852:
850:
848:
835:
830:
827:
824:
820:
809:
801:
800:
798:
796:
783:
778:
774:
763:
759:
758:
756:
753:
741:
735:
730:
726:
722:
717:
712:
708:
703:
699:
696:
686:
682:
681:
678:
675:
672:
652:
647:
643:
620:
615:
611:
584:
579:
575:
552:
547:
543:
514:
511:
463:L. K. Schubert
440:In mid 1960s,
433:
430:
397:
396:Quantum models
394:
359:Zeno's paradox
338:
335:
334:
333:
332:
331:
315:
314:
313:
298:
297:
296:
265:
252:
251:
217:
215:
208:
202:
199:
190:
187:
170:
166:
161:
133:
129:
115:
112:
108:undecidability
85:
82:
67:Turing machine
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3061:
3050:
3047:
3045:
3042:
3041:
3039:
3028:
3022:
3018:
3013:
3006:
3002:
2998:
2994:
2990:
2983:
2978:
2974:
2970:
2965:
2960:
2956:
2952:
2948:
2943:
2939:
2935:
2931:
2927:
2923:
2919:
2914:
2904:
2900:
2896:
2892:
2887:
2882:
2877:
2873:
2869:
2865:
2861:
2857:
2853:
2846:
2841:
2834:
2830:
2826:
2822:
2818:
2814:
2810:
2803:
2798:
2794:
2790:
2786:
2782:
2777:
2772:
2768:
2764:
2759:
2749:on 2011-07-24
2745:
2741:
2734:
2729:
2725:
2721:
2717:
2712:
2708:
2706:0-387-95569-0
2702:
2698:
2693:
2689:
2685:
2680:
2670:on 2017-02-06
2666:
2662:
2658:
2651:
2646:
2645:
2641:
2630:
2629:
2621:
2618:
2613:
2606:
2603:
2598:
2594:
2590:
2586:
2579:
2576:
2570:
2565:
2561:
2557:
2553:
2549:
2543:
2540:
2534:
2529:
2525:
2521:
2517:
2513:
2509:
2503:
2500:
2495:
2491:
2487:
2483:
2479:
2475:
2471:
2467:
2463:
2459:
2452:
2445:
2442:
2437:
2433:
2428:
2427:gr-qc/0609035
2423:
2419:
2415:
2411:
2405:
2402:
2397:
2391:
2383:
2377:
2373:
2372:
2367:
2366:Stephen Smale
2363:
2357:
2354:
2349:
2345:
2341:
2337:
2332:
2327:
2323:
2319:
2312:
2309:
2304:
2300:
2296:
2292:
2287:
2282:
2278:
2274:
2270:
2263:
2260:
2254:
2249:
2242:
2239:
2234:
2230:
2225:
2220:
2216:
2212:
2208:
2201:
2199:
2195:
2190:
2186:
2182:
2178:
2174:
2170:
2166:
2162:
2155:
2153:
2149:
2143:
2138:
2134:
2130:
2126:
2118:
2114:
2110:
2106:
2102:
2098:
2094:
2090:
2083:
2081:
2077:
2072:
2068:
2064:
2060:
2056:
2049:
2046:
2040:
2036:
2032:
2028:
2020:
2016:
2012:
2008:
2004:
2000:
1995:
1990:
1986:
1982:
1981:
1972:
1968:
1964:
1960:
1955:
1950:
1946:
1942:
1938:
1930:
1927:
1924:
1921:
1916:
1913:
1908:
1904:
1900:
1896:
1891:
1890:gr-qc/0209061
1886:
1882:
1878:
1871:
1868:
1863:
1859:
1855:
1851:
1847:
1843:
1836:
1833:
1828:
1824:
1820:
1816:
1811:
1810:gr-qc/0104023
1806:
1802:
1798:
1791:
1788:
1783:
1777:
1773:
1769:
1764:
1763:
1757:
1750:
1747:
1742:
1738:
1734:
1730:
1726:
1722:
1718:
1714:
1707:
1704:
1699:
1695:
1691:
1687:
1682:
1677:
1673:
1669:
1662:
1659:
1654:
1650:
1646:
1642:
1637:
1632:
1628:
1624:
1620:
1612:
1608:
1604:
1600:
1595:
1590:
1586:
1582:
1573:
1568:
1564:
1560:
1556:
1553:(June 2004).
1552:
1545:
1541:
1534:
1531:
1525:
1522:
1510:
1503:
1501:
1497:
1492:
1488:
1484:
1480:
1473:
1470:
1465:
1461:
1454:
1451:
1447:
1442:
1437:
1433:
1429:
1425:
1418:
1416:
1412:
1407:
1403:
1399:
1395:
1391:
1387:
1382:
1381:10.1.1.2.8029
1377:
1373:
1369:
1362:
1359:
1353:
1348:
1344:
1340:
1336:
1329:
1326:
1314:
1310:
1303:
1300:
1296:
1293:
1289:
1285:
1280:
1277:
1272:
1268:
1264:
1260:
1256:
1252:
1247:
1242:
1238:
1234:
1227:
1220:
1217:
1213:
1207:
1204:
1198:
1193:
1189:
1185:
1181:
1177:
1170:
1167:
1161:
1157:
1154:
1152:
1149:
1148:
1144:
1142:
1140:
1136:
1132:
1125:
1119:
1102:
1097:
1084:
1068:
1063:
1051:
1048:
1047:
1044:
1042:
1038:
1022:
1017:
1009:
1004:
999:
987:
984:
983:
980:
977:
963:
960:
957:
950:
947:
946:
943:
940:
937:
920:
912:
907:
895:
892:
891:
888:
885:
883:
882:
878:
876:
873:
872:
869:
866:
862:
860:
858:
855:
854:
851:
849:
833:
828:
825:
822:
810:
807:
803:
802:
799:
797:
781:
776:
764:
761:
760:
757:
754:
739:
733:
728:
720:
715:
710:
701:
697:
694:
687:
685:supertasking
684:
683:
679:
676:
673:
670:
669:
666:
650:
645:
618:
613:
600:
599:Turing degree
582:
577:
550:
545:
532:
528:
524:
520:
512:
510:
508:
504:
500:
496:
492:
488:
484:
480:
476:
471:
468:
464:
460:
455:
451:
447:
446:Hilary Putnam
443:
438:
431:
429:
427:
423:
419:
415:
411:
407:
403:
395:
393:
391:
387:
383:
379:
374:
372:
368:
364:
360:
357:(inspired by
356:
352:
348:
343:
336:
328:
324:
323:
320:
316:
310:
306:
305:
303:
299:
293:
292:
290:
286:
282:
278:
274:
270:
269:real computer
266:
263:
262:
261:
259:
248:
239:is available.
238:
234:
228:
227:
223:
218:This section
216:
207:
206:
200:
198:
196:
188:
186:
168:
159:
150:
146:
131:
113:
111:
109:
105:
101:
97:
96:
91:
83:
81:
79:
75:
70:
68:
63:
58:
56:
52:
48:
44:
40:
36:
32:
19:
3019:. Springer.
3016:
3005:the original
2992:
2988:
2954:
2950:
2921:
2917:
2906:. Retrieved
2902:
2886:math/0209332
2855:
2851:
2833:the original
2812:
2808:
2766:
2762:
2751:. Retrieved
2744:the original
2739:
2715:
2696:
2687:
2683:
2672:. Retrieved
2665:the original
2660:
2656:
2627:
2620:
2611:
2605:
2588:
2584:
2578:
2559:
2555:
2542:
2523:
2519:
2502:
2461:
2457:
2444:
2417:
2413:
2404:
2374:. Springer.
2370:
2356:
2324:(1): 23–33.
2321:
2317:
2311:
2276:
2272:
2262:
2241:
2214:
2210:
2167:(1): 49–57.
2164:
2160:
2132:
2128:
2095:(1): 28–48.
2092:
2088:
2062:
2058:
2048:
2030:
2026:
1984:
1978:
1944:
1940:
1929:
1915:
1880:
1876:
1870:
1845:
1841:
1835:
1800:
1796:
1790:
1761:
1749:
1716:
1712:
1706:
1671:
1667:
1661:
1629:(1): 83–96.
1626:
1622:
1587:(1): 23–33.
1584:
1580:
1562:
1558:
1543:
1540:Hermann Weyl
1533:
1524:
1512:. Retrieved
1482:
1478:
1472:
1463:
1459:
1453:
1445:
1431:
1427:
1371:
1367:
1361:
1342:
1338:
1328:
1318:23 September
1316:. Retrieved
1312:
1302:
1287:
1279:
1236:
1232:
1219:
1211:
1206:
1179:
1175:
1169:
1138:
1131:Martin Davis
1129:
938:
879:
805:
665:predicates.
516:
474:
472:
458:
439:
435:
399:
375:
371:Oron Shagrir
355:Zeno machine
346:
344:
340:
295:computation.
255:
242:
237:Editing help
219:
192:
117:
93:
87:
71:
59:
34:
30:
29:
18:Super Turing
2995:(1): 8–24.
2924:: 670–695.
2614:. Springer.
2362:Lenore Blum
1920:S. Aaronson
1551:Shagrir, O.
1485:: 143–153.
1182:: 161–228.
533:containing
442:E Mark Gold
302:fuzzy logic
149:uncountable
114:State space
90:Alan Turing
78:computation
3038:Categories
2908:2023-07-31
2753:2011-06-16
2674:2023-07-28
2591:(1): 4–7.
2548:P.D. Welch
2410:P.D. Welch
2331:cs/0412022
1594:cs/0412022
1466:: 186–193.
1297:p. 12
1162:References
867:functions
495:Kurt Gödel
467:arithmetic
386:black hole
319:finitistic
2938:248881264
2829:218585685
2771:CiteSeerX
2769:: 72–82.
2390:cite book
1862:122764068
1848:: 22–42.
1741:120917288
1681:1105.0047
1631:CiteSeerX
1398:0933-5846
1376:CiteSeerX
1241:CiteSeerX
1126:Criticism
1117:are r.e.
1094:Π
1060:Δ
1014:Π
1010:∪
996:Σ
904:Δ
819:Δ
773:Δ
725:Π
707:Σ
698:
642:Σ
610:Δ
574:Π
542:Σ
351:supertask
245:July 2023
165:ℵ
128:ℵ
2550:(2009).
2514:(1994).
2494:17495161
2486:17756722
2368:(1998).
2189:44655062
2117:33811657
1907:16136314
1827:17081866
1698:16816151
1542:(1927).
1406:12513452
1263:22295978
1145:See also
347:complete
312:forever.
300:Certain
151:number (
104:naturals
2973:7406983
2872:9857468
2793:1487739
2466:Bibcode
2458:Science
2348:6749770
2291:Bibcode
2233:2071951
2181:2270581
2109:2270580
2019:9879859
1999:Bibcode
1971:6634980
1721:Bibcode
1611:6749770
1514:Apr 26,
1271:5826757
808:times)
412:-model
84:History
3023:
2971:
2936:
2870:
2827:
2791:
2773:
2703:
2492:
2484:
2378:
2346:
2231:
2187:
2179:
2115:
2107:
2017:
1969:
1905:
1860:
1825:
1778:
1739:
1696:
1653:253434
1651:
1633:
1609:
1404:
1396:
1378:
1269:
1261:
1243:
1041:t-norm
677:Notes
671:Model
519:oracle
220:is in
189:Models
100:oracle
3008:(PDF)
2985:(PDF)
2969:S2CID
2934:S2CID
2881:arXiv
2868:S2CID
2848:(PDF)
2836:(PDF)
2825:S2CID
2805:(PDF)
2789:S2CID
2747:(PDF)
2736:(PDF)
2668:(PDF)
2653:(PDF)
2632:(PDF)
2490:S2CID
2454:(PDF)
2422:arXiv
2344:S2CID
2326:arXiv
2281:arXiv
2248:arXiv
2229:S2CID
2185:S2CID
2177:JSTOR
2113:S2CID
2105:JSTOR
2015:S2CID
1989:arXiv
1967:S2CID
1949:arXiv
1903:S2CID
1885:arXiv
1858:S2CID
1823:S2CID
1805:arXiv
1737:S2CID
1694:S2CID
1676:arXiv
1674:(3).
1649:S2CID
1607:S2CID
1589:arXiv
1402:S2CID
1267:S2CID
1229:(PDF)
680:Refs
410:qubit
330:time.
226:prose
3021:ISBN
2701:ISBN
2482:PMID
2396:link
2376:ISBN
1776:ISBN
1615:and
1516:2011
1394:ISSN
1320:2011
1259:PMID
459:sure
444:and
277:real
222:list
60:The
2997:doi
2993:178
2959:doi
2926:doi
2922:608
2860:doi
2817:doi
2781:doi
2767:178
2720:doi
2688:270
2593:doi
2589:178
2564:doi
2560:410
2528:doi
2524:131
2474:doi
2462:268
2432:doi
2336:doi
2322:358
2299:doi
2219:doi
2169:doi
2137:doi
2097:doi
2067:doi
2035:doi
2031:178
2007:doi
1975:or
1959:doi
1895:doi
1850:doi
1815:doi
1768:doi
1729:doi
1686:doi
1641:doi
1599:doi
1585:358
1567:doi
1563:317
1487:doi
1483:178
1436:doi
1432:317
1386:doi
1347:doi
1343:131
1251:doi
1192:hdl
1184:doi
881:HYP
565:or
521:or
428:).
365:(a
197:).
53:in
33:or
3040::
2991:.
2987:.
2967:.
2953:.
2949:.
2932:.
2920:.
2901:.
2866:.
2856:74
2854:.
2850:.
2823:.
2813:12
2811:.
2807:.
2787:.
2779:.
2765:.
2718:.
2686:.
2661:13
2659:.
2655:.
2587:.
2558:.
2554:.
2522:.
2518:.
2510:;
2488:.
2480:.
2472:.
2460:.
2456:.
2430:.
2418:59
2416:.
2392:}}
2388:{{
2342:.
2334:.
2320:.
2297:.
2289:.
2277:13
2275:.
2271:.
2227:.
2215:21
2213:.
2209:.
2197:^
2183:.
2175:.
2165:30
2163:.
2151:^
2133:10
2131:.
2127:.
2121:,
2111:.
2103:.
2093:30
2091:.
2079:^
2063:26
2061:.
2057:.
2029:.
2013:.
2005:.
1997:.
1985:44
1983:.
1965:.
1957:.
1945:42
1943:.
1939:.
1901:.
1893:.
1881:16
1879:.
1856:.
1846:60
1844:.
1821:.
1813:.
1801:41
1799:.
1774:.
1735:.
1727:.
1715:.
1692:.
1684:.
1672:22
1670:.
1647:.
1639:.
1627:21
1625:.
1621:.
1605:.
1597:.
1583:.
1577:,
1561:.
1557:.
1499:^
1481:.
1464:37
1462:.
1444:.
1430:.
1426:.
1414:^
1400:.
1392:.
1384:.
1372:41
1370:.
1341:.
1337:.
1311:.
1265:.
1257:.
1249:.
1237:24
1235:.
1231:.
1190:.
1180:45
1178:.
1141:"
695:tt
509:.
267:A
57:.
3029:.
2999::
2975:.
2961::
2955:2
2940:.
2928::
2911:.
2889:.
2883::
2874:.
2862::
2819::
2795:.
2783::
2756:.
2726:.
2722::
2709:.
2677:.
2599:.
2595::
2572:.
2566::
2536:.
2530::
2496:.
2476::
2468::
2438:.
2434::
2424::
2398:)
2384:.
2350:.
2338::
2328::
2305:.
2301::
2293::
2283::
2256:.
2250::
2235:.
2221::
2191:.
2171::
2145:.
2139::
2119:.
2099::
2073:.
2069::
2043:.
2041:.
2037::
2021:.
2009::
2001::
1991::
1973:.
1961::
1951::
1909:.
1897::
1887::
1864:.
1852::
1829:.
1817::
1807::
1784:.
1770::
1743:.
1731::
1723::
1717:5
1700:.
1688::
1678::
1655:.
1643::
1613:.
1601::
1591::
1575:.
1569::
1546:.
1518:.
1493:.
1489::
1438::
1408:.
1388::
1355:.
1349::
1322:.
1273:.
1253::
1214:)
1200:.
1194::
1186::
1103:1
1098:1
1069:1
1064:1
1023:0
1018:1
1005:0
1000:1
964:I
961:Q
958:A
939:f
924:]
921:f
918:[
913:0
908:1
834:0
829:1
826:+
823:k
806:k
782:0
777:2
740:)
734:0
729:1
721:,
716:0
711:1
702:(
651:0
646:2
619:0
614:2
583:0
578:1
551:0
546:1
247:)
243:(
229:.
169:0
160:2
132:0
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
