338:) or limit the power of flow-control instructions (for example, providing only loops that iterate over the items of an existing array). However, another theorem shows that there are problems solvable by Turing-complete languages that cannot be solved by any language with only finite looping abilities (i.e., languages that guarantee that every program will eventually finish to a halt). So any such language is not Turing-complete. For example, a language in which programs are guaranteed to complete and halt cannot compute the computable function produced by
230:(1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing-complete.
637:, etc.) are also Turing-complete. This illustrates one reason why relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing-complete.
982:
Arguably, T C computation is the only paradigm for the theory underpinning
Computer Science...It has been argued that, at present, the dominant Computer Science paradigm may be characterised theoretically as TC computation, overarching programming languages, and practically as Computational Thinking,
280:
computer. Zuse was not familiar with Turing's work on computability at the time. In particular, the Z3 lacked dedicated facilities for a conditional jump, thereby precluding it from being Turing complete. However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps,
110:
usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language. In real life, this leads to the
186:
A system is called universal with respect to a class of systems if it can compute every function computable by systems in that class (or can simulate each of those systems). Typically, the term 'universality' is tacitly used with respect to a Turing-complete class of systems. The term "weakly
122:
Real computers constructed so far can be functionally analyzed like a single-tape Turing machine (which uses a "tape" for memory); thus the associated mathematics can apply by abstracting their operation far enough. However, real computers have limited physical resources, so they are only
245:
led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction that could be performed by a machine. Soon it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved by
97:
To show that something is Turing-complete, it is enough to demonstrate that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.
609:
Turing completeness is an abstract statement of ability, rather than a prescription of specific language features used to implement that ability. The features used to achieve Turing completeness can be quite different; Fortran systems would use loop constructs or possibly even
75:). This means that this system is able to recognize or decode other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete.
330:
This impossibility poses problems when analyzing real-world computer programs. For example, one cannot write a tool that entirely protects programmers from writing infinite loops or protects users from supplying input that would cause infinite loops.
176:. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known physically-implementable Turing-complete systems are Turing-equivalent, which adds support to the
2265:
241:. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop. In the early 20th century,
311:
and under what circumstances. The first result of computability theory is that there exist problems for which it is impossible to predict what a (Turing-complete) system will do over an arbitrarily long time.
269:, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
257:. This theorem showed that axiom systems were limited when reasoning about the computation that deduces their theorems. Church and Turing independently demonstrated that Hilbert's
172:
A Turing-complete system is called Turing-equivalent if every function it can compute is also Turing-computable; i.e., it computes precisely the same class of functions as do
323:
program, and determines whether the program, operating on the input, will eventually stop or will continue forever. It is trivial to create an algorithm that can do this for
368:), since there are only countably many computations but uncountably many oracles. So a computer with a random Turing oracle can compute things that a Turing machine cannot.
327:
inputs, but impossible to do this in general. For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold.
443:(their abstract models, maybe with some particular constructs that assume finite memory omitted), conventional and unconventional, are Turing-complete. This includes:
281:
and therefore Turing complete in theory. To do this, its tape program would have to be long enough to execute every possible path through both sides of every branch.
212:
states that this is a law of mathematics – that a universal Turing machine can, in principle, perform any calculation that any other programmable
90:
can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine. A
1306:
390:
itself is computable on a universal Turing machine. This would imply that no computer more powerful than a universal Turing machine can be built physically.
220:, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation.
356:
A computer with access to an infinite tape of data may be more powerful than a Turing machine: for instance, the tape might contain the solution to the
630:
596:
in which programmers work out how to achieve basic programming constructs in an extremely difficult but mathematically Turing-equivalent language.
265:(decision problem) was unsolvable, thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on
2315:
2198:
1970:
1466:
1165:
1420:
1341:
2348:
2286:
464:
254:
1262:
648:, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.
382:
All known laws of physics have consequences that are computable by a series of approximations on a digital computer. A hypothesis called
2293:
1785:
Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (October 2013).
482:
2272:
402:. They are intended to be as simple as possible, so that it would be easier to understand the limits of computation. Here are a few:
2090:
2056:
1602:
1290:
1045:
1494:
1446:
94:
can be used to simulate any Turing machine and by extension the purely computational aspects of any possible real-world computer.
862:. All of these compute proper subsets of the total computable functions, since the full set of total computable functions is not
622:, which have memory (RAM and register) and a control unit. These two elements make this architecture Turing-complete. Even pure
2067:
553:
1683:
2338:
1561:
896:
839:
537:
476:
398:
The computational systems (algebras, calculi) that are discussed as Turing-complete systems are those intended for studying
1982:
589:
514:
458:
339:
1734:; Chen, Yuan-Jyue; Reif, John (4 May 2020). "Using Strand Displacing Polymerase To Program Chemical Reaction Networks".
878:
859:
831:
399:
238:
1364:
855:
533:
468:
1091:
Rojas, RaĂşl (1 February 2014). "Konrad Zuse und der bedingte Sprung" [Konrad Zuse and the conditional jump].
835:
284:
The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the
1646:
947:
867:
863:
486:
266:
143:, several closely related terms are used to describe the computational power of a computational system (such as an
2191:
926:
1196:
906:
377:
319:: create an algorithm that takes as input a program in some Turing-complete language and some data to be fed to
209:
204:
Turing completeness is significant in that every real-world design for a computing device can be simulated by a
177:
83:
1230:
731:
710:
619:
518:
454:
205:
163:
124:
91:
2136:
Turing, A. M. (1938). "On
Computable Numbers, with an Application to the Entscheidungsproblem: A correction".
1004:
Michaelson, Greg (14 February 2020). "Programming
Paradigms, Turing Completeness and Computational Thinking".
655:
428:
1392:
131:
is defined as a device with a Turing-complete instruction set, infinite memory, and infinite available time.
82: – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The
2343:
1035:
593:
563:
557:
529:
450:
17:
2310:
1850:
Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 December 2017).
962:
768:
162:
is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a
2184:
1912:
1798:
1142:, Lecture Notes in Computer Science, vol. 1337, Berlin, Heidelberg: Springer, pp. 201–208,
911:
812:
804:
758:
724:
440:
304:
300:
260:
148:
140:
52:
44:
40:
1619:
1017:
2279:
1589:
Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (August 2015).
623:
335:
159:
2101:
2012:
2124:
2040:
1767:
1397:
1333:
1171:
1143:
1116:
808:
800:
659:
614:
statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use
188:
128:
56:
819:. Further examples include some of the early versions of the pixel shader languages embedded in
807:. A more powerful but still not Turing-complete extension of finite automata is the category of
795:
Many computational languages exist that are not Turing-complete. One such example is the set of
2238:
2086:
2052:
2004:
1948:
1930:
1881:
1873:
1832:
1814:
1759:
1751:
1598:
1567:
1557:
1286:
1253:
1161:
1108:
1041:
931:
901:
779:
543:
234:
227:
753:
2243:
2145:
2116:
1994:
1986:
1938:
1920:
1863:
1822:
1806:
1743:
1153:
1100:
1073:
1013:
921:
796:
703:
433:
217:
144:
31:
292:
computer was operational in 1945, but it did not support conditional branching until 1950.
30:
For the usage of this term in the theory of relative computability by oracle machines, see
1710:
Break Me00 The MoVfuscator
Turning mov into a soul crushing RE nightmare Christopher Domas
891:
874:
847:
685:
641:
423:
417:
406:
383:
357:
316:
223:
48:
1916:
1802:
1501:
1261:(Technical report). Institute for Computing Science, University of Texas at Austin. 37.
1134:
Schmidhuber, JĂĽrgen (1997), Freksa, Christian; Jantzen, Matthias; Valk, RĂĽdiger (eds.),
2233:
2228:
1999:
1943:
1900:
1827:
1786:
1526:
957:
851:
696:
603:
411:
351:
192:
173:
112:
68:
2332:
2223:
2072:
2045:
1771:
1731:
1550:
1031:
952:
783:
506:
365:
361:
308:
289:
277:
247:
242:
1334:"Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine"
1175:
360:
or some other Turing-undecidable problem. Such an infinite tape of data is called a
1966:
1471:
1120:
843:
1527:"Habbo's Twitter thread on the implementation of a Turing machine inside the game"
2128:
1590:
1280:
815:, which are commonly used to generate parse trees in an initial stage of program
2248:
2207:
936:
742:
675:
494:
273:
72:
2149:
2120:
1061:
1104:
916:
763:
502:
334:
One can instead limit a program to executing only for a fixed period of time (
191:) whose universality is achieved only by modifying the standard definition of
107:
1934:
1877:
1818:
1755:
1112:
842:, all functions are total and must terminate. Charity uses a type system and
1925:
1868:
1851:
1584:
1571:
717:
615:
472:
87:
2008:
1990:
1952:
1885:
1836:
1810:
1763:
1708:
1552:
Effective C++ : 55 specific ways to improve your programs and designs
2165:
1747:
1687:
1148:
866:. Also, since all functions in these languages are total, algorithms for
820:
816:
671:
651:
645:
387:
213:
116:
2102:"On Computable Numbers, with an Application to the Entscheidungsproblem"
1657:
870:
cannot be written in these languages, in contrast with Turing machines.
253:
The actual notion of computation was isolated soon after, starting with
1157:
498:
1591:"Control-flow bending: on the effectiveness of control-flow integrity"
1077:
1467:"It's possible to build a Turing machine within Magic: The Gathering"
1369:
1135:
858:
language is designed so that it computes only the functions that are
824:
547:
1971:"A Mechanical Turing Machine: Blueprint for a Biomolecular Computer"
1222:
1136:"A computer scientist's view of life, the universe, and everything"
490:
1899:
Soloveichik, David; Seelig, Georg; Winfree, Erik (23 March 2010).
634:
285:
86:
conjectures that any function whose values can be computed by an
611:
577:
571:
510:
2180:
1595:
Proceedings of the 24th USENIX Conference on
Security Symposium
1421:"This 8-bit processor built in Minecraft can run its own games"
1140:
Foundations of
Computer Science: Potential — Theory — Cognition
2176:
1307:"Announcing LAMBDA: Turn Excel formulas into custom functions"
629:
Turing completeness in declarative SQL is implemented through
583:
567:
1684:"One Instruction To Rule Them All: C Compiler Emits Only MOV"
644:
is Turing-complete, but many typed lambda calculi, including
187:
universal" is sometimes used to distinguish a system (e.g. a
618:. Most programming languages are describing computations on
216:
can. This says nothing about the effort needed to write the
1445:
Churchill, Alex; Biderman, Stella; Herrick, Austin (2020).
364:. Even a Turing oracle with random data is not computable (
1255:
71:(devised by English mathematician and computer scientist
27:
Ability of a computing system to simulate Turing machines
1556:(3rd ed.). Upper Saddle River, NJ: Addison-Wesley.
1454:. 10th International Conference on Fun with Algorithms.
1282:
Parallel programming: for multicore and cluster systems
195:
so as to include input streams with infinitely many 1s.
1730:
Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis;
1495:"Infinite versions of minesweeper are Turing complete"
1365:"Cities: Skylines Map Becomes A Poop-Powered Computer"
378:
Church–Turing thesis § Philosophical implications
2068:"Simplest 'universal computer' wins student $ 25,000"
678:
are Turing-complete by accident, i.e. not by design.
158:
A computational system that can compute every Turing-
1901:"DNA as a universal substrate for chemical kinetics"
2303:
2257:
2083:
The
Universal Turing Machine: A Half-Century Survey
307:to analyze problems and determine whether they are
2044:
1549:
1787:"Programmable chemical controllers made from DNA"
1393:"Opus Magnum player makes an alchemical computer"
1252:Boyer, Robert S.; Moore, J. Strother (May 1983).
43:, a system of data-manipulation rules (such as a
1006:The Art, Science, and Engineering of Programming
633:. Unsurprisingly, procedural extensions to SQL (
1905:Proceedings of the National Academy of Sciences
250:in 1930 to be enough to produce every theorem.
2138:Proceedings of the London Mathematical Society
2109:Proceedings of the London Mathematical Society
342:on all computable functions in that language.
237:formulated notions of computability, defining
2192:
127:complete. In contrast, the abstraction of a
8:
1852:"Enzyme-free nucleic acid dynamical systems"
1062:"How to make Zuse's Z3 a universal computer"
526:Most languages using less common paradigms:
386:states that this is no accident because the
258:
447:All general-purpose languages in wide use.
2199:
2185:
2177:
18:Turing equivalence (theory of computation)
1998:
1942:
1924:
1867:
1826:
1147:
1018:10.22152/programming-journal.org/2020/4/4
580:and other hardware description languages.
1736:Journal of the American Chemical Society
1448:Magic: The Gathering Is Turing Complete
1279:Rauber, Thomas; RĂĽnger, Gudula (2013).
1268:from the original on 22 September 2017.
996:
975:
786:have been shown to be Turing-equivalent
1548:Meyers, Scott (Scott Douglas) (2005).
1391:Caldwell, Brendan (20 November 2017).
1040:, London: Burnett Books, p. 111,
983:overarching programming methodologies.
1227:B2B Integration Solutions from Unidex
7:
2287:Computing Machinery and Intelligence
1620:"TypeScript and Turing Completeness"
1465:Ouellette, Jennifer (23 June 2019).
1195:Dfetter; Breinbaas (8 August 2011).
2294:The Chemical Basis of Morphogenesis
2273:Systems of Logic Based on Ordinals
1618:Dabler, Ryan (23 September 2021).
1223:"Universal Turing Machine in XSLT"
1066:Annals of the History of Computing
631:recursive common table expressions
67:if it can be used to simulate any
25:
1344:from the original on 27 June 2015
1332:Cedotal, Andrew (16 April 2010).
1233:from the original on 17 July 2011
666:Unintentional Turing completeness
111:practical concepts of computing
1363:Plunkett, Luke (16 July 2019).
554:General-purpose macro processor
2066:Giles, Jim (24 October 2007).
1682:Williams, Al (21 March 2021).
897:Algorithmic information theory
590:Esoteric programming languages
255:Gödel's incompleteness theorem
1:
1983:Weizmann Institute of Science
1493:Kaye, Richard (31 May 2007).
791:Non-Turing-complete languages
239:primitive recursive functions
78:A related concept is that of
1221:Lyons, Bob (30 March 2001).
879:simply typed lambda calculus
832:total functional programming
803:and which are recognized by
400:theoretical computer science
183:(Computational) universality
2349:Programming language theory
1311:TECHCOMMUNITY.MICROSOFT.COM
868:recursively enumerable sets
315:The classic example is the
267:general recursive functions
2365:
2081:Herken, Rolf, ed. (1995).
1285:(2nd ed.). Springer.
948:Structured program theorem
784:enzyme-based DNA computers
780:Chemical reaction networks
375:
349:
340:Cantor's diagonal argument
233:In the late 19th century,
29:
2214:
1105:10.1007/s00287-013-0717-9
927:Machine that always halts
799:, which are generated by
749:Computational languages:
620:von Neumann architectures
65:computationally universal
2150:10.1112/plms/s2-43.6.544
2121:10.1112/plms/s2-42.1.230
1647:"mov is Turing-complete"
764:TypeScript's type system
206:universal Turing machine
164:universal Turing machine
125:linear bounded automaton
92:universal Turing machine
1926:10.1073/pnas.0909380107
1869:10.1126/science.aal2052
1037:Alan Turing: The Enigma
850:, whereas Epigram uses
662:, are Turing-complete.
594:mathematical recreation
586:, a typesetting system.
2100:Turing, A. M. (1936).
1991:10.1098/rsfs.2011.0118
1811:10.1038/nnano.2013.189
451:Procedural programming
420:(language recognizers)
259:
102:Non-mathematical usage
2339:Theory of computation
2311:Legacy of Alan Turing
2280:Intelligent Machinery
2266:On Computable Numbers
2047:Theory of Computation
1791:Nature Nanotechnology
963:Emulation (computing)
864:computably enumerable
813:context-free grammars
656:Conway's Game of Life
626:are Turing-complete.
606:are Turing-complete.
441:programming languages
414:(language generators)
305:models of computation
1748:10.1021/jacs.0c02240
1597:. pp. 161–176.
1060:Rojas, Raul (1998).
912:Computability theory
907:Church–Turing thesis
877:is Turing-complete,
759:printf format string
725:Magic: The Gathering
624:functional languages
429:Post–Turing machines
301:Computability theory
296:Computability theory
261:Entscheidungsproblem
210:Church–Turing thesis
178:Church–Turing thesis
149:programming language
141:computability theory
84:Church–Turing thesis
53:programming language
45:model of computation
41:computability theory
2219:Turing completeness
2085:. Springer Verlag.
1969:(7 December 1999).
1917:2010PNAS..107.5393S
1803:2013NatNa...8..755C
1663:on 14 February 2021
1585:A 27th IOCCC Winner
1197:"Cyclic Tag System"
1093:Informatik-Spektrum
873:Although (untyped)
860:primitive recursive
834:languages, such as
801:regular expressions
160:computable function
155:Turing completeness
1862:(6369): eaal2052.
1398:Rock Paper Shotgun
1158:10.1007/bfb0052088
844:control constructs
771:'s MOV instruction
566:languages such as
546:languages such as
532:languages such as
485:languages such as
467:languages such as
453:languages such as
366:with probability 1
189:cellular automaton
169:Turing equivalence
135:Formal definitions
129:universal computer
80:Turing equivalence
57:cellular automaton
2326:
2325:
2166:"Turing Complete"
2039:Brainerd, W. S.;
2015:on 3 January 2009
1911:(12): 5393–5398.
1742:(21): 9587–9593.
1529:. 9 November 2020
1419:Crider, Michael.
1313:. 3 December 2020
1167:978-3-540-69640-7
1078:10.1109/85.707574
902:Chomsky hierarchy
809:pushdown automata
797:regular languages
660:cellular automata
544:Logic programming
235:Leopold Kronecker
228:analytical engine
16:(Redirected from
2356:
2244:Turing reduction
2201:
2194:
2187:
2178:
2173:
2153:
2132:
2106:
2096:
2077:
2062:
2050:
2041:Landweber, L. H.
2025:
2024:
2022:
2020:
2011:. Archived from
2002:
1963:
1957:
1956:
1946:
1928:
1896:
1890:
1889:
1871:
1847:
1841:
1840:
1830:
1782:
1776:
1775:
1727:
1721:
1720:
1719:
1717:
1705:
1699:
1698:
1696:
1694:
1679:
1673:
1672:
1670:
1668:
1662:
1656:. Archived from
1651:
1645:Dolan, Stephen.
1642:
1636:
1635:
1633:
1631:
1615:
1609:
1608:
1582:
1576:
1575:
1555:
1545:
1539:
1538:
1536:
1534:
1523:
1517:
1516:
1514:
1512:
1507:on 3 August 2016
1506:
1500:. Archived from
1499:
1490:
1484:
1483:
1481:
1479:
1462:
1456:
1455:
1453:
1442:
1436:
1435:
1433:
1431:
1416:
1410:
1409:
1407:
1405:
1388:
1382:
1381:
1379:
1377:
1360:
1354:
1353:
1351:
1349:
1329:
1323:
1322:
1320:
1318:
1303:
1297:
1296:
1276:
1270:
1269:
1267:
1260:
1249:
1243:
1242:
1240:
1238:
1218:
1212:
1211:
1209:
1207:
1192:
1186:
1185:
1184:
1182:
1151:
1149:quant-ph/9904050
1131:
1125:
1124:
1088:
1082:
1081:
1057:
1051:
1050:
1028:
1022:
1021:
1001:
984:
980:
922:Loop (computing)
704:Cities: Skylines
434:Process calculus
288:in 1946. Zuse's
264:
145:abstract machine
59:) is said to be
32:Turing reduction
21:
2364:
2363:
2359:
2358:
2357:
2355:
2354:
2353:
2329:
2328:
2327:
2322:
2299:
2253:
2210:
2205:
2164:
2161:
2156:
2135:
2104:
2099:
2093:
2080:
2065:
2059:
2038:
2034:
2032:Further reading
2029:
2028:
2018:
2016:
1975:Interface Focus
1965:
1964:
1960:
1898:
1897:
1893:
1849:
1848:
1844:
1797:(10): 755–762.
1784:
1783:
1779:
1729:
1728:
1724:
1715:
1713:
1707:
1706:
1702:
1692:
1690:
1681:
1680:
1676:
1666:
1664:
1660:
1649:
1644:
1643:
1639:
1629:
1627:
1617:
1616:
1612:
1605:
1588:
1587:
1583:
1579:
1564:
1547:
1546:
1542:
1532:
1530:
1525:
1524:
1520:
1510:
1508:
1504:
1497:
1492:
1491:
1487:
1477:
1475:
1464:
1463:
1459:
1451:
1444:
1443:
1439:
1429:
1427:
1418:
1417:
1413:
1403:
1401:
1390:
1389:
1385:
1375:
1373:
1362:
1361:
1357:
1347:
1345:
1331:
1330:
1326:
1316:
1314:
1305:
1304:
1300:
1293:
1278:
1277:
1273:
1265:
1258:
1251:
1250:
1246:
1236:
1234:
1220:
1219:
1215:
1205:
1203:
1201:PostgreSQL wiki
1194:
1193:
1189:
1180:
1178:
1168:
1133:
1132:
1128:
1090:
1089:
1085:
1059:
1058:
1054:
1048:
1030:
1029:
1025:
1003:
1002:
998:
993:
988:
987:
981:
977:
972:
967:
941:
892:AI-completeness
887:
875:lambda calculus
852:dependent types
848:category theory
805:finite automata
793:
686:Microsoft Excel
668:
642:lambda calculus
604:rewrite systems
465:Object-oriented
424:Lambda calculus
418:Formal language
407:Automata theory
396:
384:digital physics
380:
374:
372:Digital physics
358:halting problem
354:
348:
317:halting problem
298:
224:Charles Babbage
202:
174:Turing machines
137:
104:
61:Turing-complete
49:instruction set
47:, a computer's
35:
28:
23:
22:
15:
12:
11:
5:
2362:
2360:
2352:
2351:
2346:
2344:Turing machine
2341:
2331:
2330:
2324:
2323:
2321:
2320:
2319:
2318:
2307:
2305:
2301:
2300:
2298:
2297:
2290:
2283:
2276:
2269:
2261:
2259:
2255:
2254:
2252:
2251:
2246:
2241:
2239:Turing's proof
2236:
2234:Turing pattern
2231:
2229:Turing machine
2226:
2221:
2215:
2212:
2211:
2206:
2204:
2203:
2196:
2189:
2181:
2175:
2174:
2160:
2159:External links
2157:
2155:
2154:
2133:
2097:
2091:
2078:
2063:
2057:
2035:
2033:
2030:
2027:
2026:
1958:
1891:
1842:
1777:
1732:Strauss, Karin
1722:
1700:
1674:
1637:
1610:
1603:
1577:
1562:
1540:
1518:
1485:
1457:
1437:
1411:
1383:
1355:
1324:
1298:
1291:
1271:
1244:
1213:
1187:
1166:
1126:
1083:
1052:
1046:
1032:Hodges, Andrew
1023:
995:
994:
992:
989:
986:
985:
974:
973:
971:
968:
966:
965:
960:
958:Virtualization
955:
950:
945:
939:
934:
932:Rice's theorem
929:
924:
919:
914:
909:
904:
899:
894:
888:
886:
883:
792:
789:
788:
787:
773:
772:
766:
761:
756:
747:
746:
737:Social media:
735:
734:
730:Infinite-grid
728:
721:
714:
707:
700:
697:Dwarf Fortress
689:
688:
667:
664:
600:
599:
598:
597:
587:
581:
575:
561:
551:
541:
524:
523:
522:
483:Multi-paradigm
480:
462:
437:
436:
431:
426:
421:
415:
412:Formal grammar
409:
395:
392:
373:
370:
352:Oracle machine
350:Main article:
347:
346:Turing oracles
344:
297:
294:
276:completed the
201:
198:
197:
196:
193:Turing machine
184:
181:
170:
167:
156:
136:
133:
113:virtualization
103:
100:
69:Turing machine
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2361:
2350:
2347:
2345:
2342:
2340:
2337:
2336:
2334:
2317:
2314:
2313:
2312:
2309:
2308:
2306:
2302:
2295:
2291:
2288:
2284:
2281:
2277:
2274:
2270:
2267:
2263:
2262:
2260:
2256:
2250:
2247:
2245:
2242:
2240:
2237:
2235:
2232:
2230:
2227:
2225:
2224:Turing degree
2222:
2220:
2217:
2216:
2213:
2209:
2202:
2197:
2195:
2190:
2188:
2183:
2182:
2179:
2171:
2167:
2163:
2162:
2158:
2151:
2147:
2143:
2139:
2134:
2130:
2126:
2122:
2118:
2114:
2110:
2103:
2098:
2094:
2092:3-211-82637-8
2088:
2084:
2079:
2075:
2074:
2073:New Scientist
2069:
2064:
2060:
2058:0-471-09585-0
2054:
2049:
2048:
2042:
2037:
2036:
2031:
2014:
2010:
2006:
2001:
1996:
1992:
1988:
1984:
1980:
1976:
1972:
1968:
1967:Shapiro, Ehud
1962:
1959:
1954:
1950:
1945:
1940:
1936:
1932:
1927:
1922:
1918:
1914:
1910:
1906:
1902:
1895:
1892:
1887:
1883:
1879:
1875:
1870:
1865:
1861:
1857:
1853:
1846:
1843:
1838:
1834:
1829:
1824:
1820:
1816:
1812:
1808:
1804:
1800:
1796:
1792:
1788:
1781:
1778:
1773:
1769:
1765:
1761:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1726:
1723:
1712:
1711:
1704:
1701:
1689:
1685:
1678:
1675:
1659:
1655:
1648:
1641:
1638:
1625:
1621:
1614:
1611:
1606:
1604:9781931971232
1600:
1596:
1592:
1586:
1581:
1578:
1573:
1569:
1565:
1559:
1554:
1553:
1544:
1541:
1528:
1522:
1519:
1503:
1496:
1489:
1486:
1474:
1473:
1468:
1461:
1458:
1450:
1449:
1441:
1438:
1426:
1422:
1415:
1412:
1400:
1399:
1394:
1387:
1384:
1372:
1371:
1366:
1359:
1356:
1343:
1339:
1335:
1328:
1325:
1312:
1308:
1302:
1299:
1294:
1292:9783642378010
1288:
1284:
1283:
1275:
1272:
1264:
1257:
1256:
1248:
1245:
1232:
1228:
1224:
1217:
1214:
1202:
1198:
1191:
1188:
1177:
1173:
1169:
1163:
1159:
1155:
1150:
1145:
1141:
1137:
1130:
1127:
1122:
1118:
1114:
1110:
1106:
1102:
1098:
1095:(in German).
1094:
1087:
1084:
1079:
1075:
1071:
1067:
1063:
1056:
1053:
1049:
1047:0-04-510060-8
1043:
1039:
1038:
1033:
1027:
1024:
1019:
1015:
1011:
1007:
1000:
997:
990:
979:
976:
969:
964:
961:
959:
956:
954:
953:Turing tarpit
951:
949:
946:
944:
942:
935:
933:
930:
928:
925:
923:
920:
918:
915:
913:
910:
908:
905:
903:
900:
898:
895:
893:
890:
889:
884:
882:
880:
876:
871:
869:
865:
861:
857:
853:
849:
845:
841:
837:
833:
828:
826:
822:
818:
814:
810:
806:
802:
798:
790:
785:
781:
778:
777:
776:
770:
767:
765:
762:
760:
757:
755:
754:C++ templates
752:
751:
750:
745:
744:
740:
739:
738:
733:
729:
727:
726:
722:
720:
719:
715:
713:
712:
708:
706:
705:
701:
699:
698:
694:
693:
692:
687:
684:
683:
682:
679:
677:
673:
665:
663:
661:
657:
653:
649:
647:
643:
638:
636:
632:
627:
625:
621:
617:
613:
607:
605:
595:
591:
588:
585:
582:
579:
576:
573:
569:
565:
562:
559:
555:
552:
549:
545:
542:
539:
535:
531:
528:
527:
525:
520:
516:
512:
508:
507:Object Pascal
504:
500:
496:
492:
488:
484:
481:
478:
474:
470:
466:
463:
460:
456:
452:
449:
448:
446:
445:
444:
442:
435:
432:
430:
427:
425:
422:
419:
416:
413:
410:
408:
405:
404:
403:
401:
393:
391:
389:
385:
379:
371:
369:
367:
363:
362:Turing oracle
359:
353:
345:
343:
341:
337:
332:
328:
326:
322:
318:
313:
310:
306:
302:
295:
293:
291:
287:
282:
279:
275:
270:
268:
263:
262:
256:
251:
249:
244:
243:David Hilbert
240:
236:
231:
229:
225:
221:
219:
215:
211:
207:
199:
194:
190:
185:
182:
179:
175:
171:
168:
165:
161:
157:
154:
153:
152:
150:
146:
142:
134:
132:
130:
126:
120:
118:
114:
109:
101:
99:
95:
93:
89:
85:
81:
76:
74:
70:
66:
62:
58:
54:
50:
46:
42:
37:
33:
19:
2258:Publications
2218:
2169:
2141:
2137:
2112:
2108:
2082:
2071:
2046:
2017:. Retrieved
2013:the original
1978:
1974:
1961:
1908:
1904:
1894:
1859:
1855:
1845:
1794:
1790:
1780:
1739:
1735:
1725:
1714:, retrieved
1709:
1703:
1691:. Retrieved
1677:
1665:. Retrieved
1658:the original
1654:stedolan.net
1653:
1640:
1628:. Retrieved
1623:
1613:
1594:
1580:
1551:
1543:
1531:. Retrieved
1521:
1509:. Retrieved
1502:the original
1488:
1476:. Retrieved
1472:Ars Technica
1470:
1460:
1447:
1440:
1428:. Retrieved
1424:
1414:
1404:23 September
1402:. Retrieved
1396:
1386:
1374:. Retrieved
1368:
1358:
1346:. Retrieved
1338:The Mary Sue
1337:
1327:
1315:. Retrieved
1310:
1301:
1281:
1274:
1254:
1247:
1235:. Retrieved
1226:
1216:
1206:10 September
1204:. Retrieved
1200:
1190:
1179:, retrieved
1139:
1129:
1099:(1): 50–53.
1096:
1092:
1086:
1072:(3): 51–54.
1069:
1065:
1055:
1036:
1026:
1009:
1005:
999:
978:
937:
872:
829:
827:extensions.
794:
774:
769:x86 assembly
748:
741:
736:
723:
716:
709:
702:
695:
690:
680:
669:
650:
640:The untyped
639:
628:
608:
601:
592:, a form of
438:
397:
381:
355:
333:
329:
324:
320:
314:
299:
283:
271:
252:
232:
222:
203:
138:
121:
105:
96:
79:
77:
64:
60:
38:
36:
2249:Turing test
2208:Alan Turing
2170:wiki.c2.com
2144:: 544–546.
2115:: 230–265.
1985:: 497–503.
1630:12 November
1533:11 November
743:Habbo Hotel
732:Minesweeper
711:Opus Magnum
676:video games
564:Declarative
495:Common Lisp
274:Konrad Zuse
73:Alan Turing
2333:Categories
1716:5 November
1693:23 October
1563:0321334876
1317:8 December
991:References
917:Inner loop
681:Software:
530:Functional
503:JavaScript
376:See also:
309:computable
248:Kurt Gödel
108:colloquial
2316:namesakes
2051:. Wiley.
2019:13 August
1935:0027-8424
1878:0036-8075
1819:1748-3395
1772:218504535
1756:0002-7863
1113:0170-6012
1034:(1992) ,
970:Footnotes
846:based on
817:compiling
775:Biology:
718:Minecraft
616:recursion
473:Smalltalk
117:emulation
88:algorithm
2296:" (1952)
2289:" (1950)
2282:" (1948)
2275:" (1939)
2268:" (1936)
2043:(1974).
2009:22649583
1953:20203007
1886:29242317
1837:24077029
1764:32364723
1688:Hackaday
1626:. LINKIT
1572:60425273
1478:12 March
1342:Archived
1263:Archived
1231:Archived
1176:17830241
885:See also
881:is not.
821:Direct3D
672:software
652:Rule 110
646:System F
556:such as
394:Examples
388:universe
272:In 1941
214:computer
2304:Related
2000:3363030
1944:2851759
1913:Bibcode
1856:Science
1828:4150546
1799:Bibcode
1430:21 July
1425:PCWorld
1376:16 July
1121:1086397
943:theorem
840:Epigram
836:Charity
691:Games:
658:, both
538:Haskell
499:Fortran
336:timeout
218:program
200:History
55:, or a
2127:
2089:
2055:
2007:
1997:
1951:
1941:
1933:
1884:
1876:
1835:
1825:
1817:
1770:
1762:
1754:
1624:ITNEXT
1601:
1570:
1560:
1511:8 July
1370:Kotaku
1348:2 June
1289:
1237:5 July
1181:23 May
1174:
1164:
1119:
1111:
1044:
854:. The
825:OpenGL
548:Prolog
515:Python
459:Pascal
208:. The
2140:. 2.
2129:73712
2125:S2CID
2111:. 2.
2105:(PDF)
1981:(4).
1768:S2CID
1667:9 May
1661:(PDF)
1650:(PDF)
1505:(PDF)
1498:(PDF)
1452:(PDF)
1266:(PDF)
1259:(PDF)
1172:S2CID
1144:arXiv
1117:S2CID
1012:(3).
670:Some
635:PLSQL
602:Some
439:Most
303:uses
286:ENIAC
2087:ISBN
2053:ISBN
2021:2009
2005:PMID
1949:PMID
1931:ISSN
1882:PMID
1874:ISSN
1833:PMID
1815:ISSN
1760:PMID
1752:ISSN
1718:2022
1695:2023
1669:2019
1632:2022
1599:ISBN
1568:OCLC
1558:ISBN
1535:2020
1513:2016
1480:2023
1432:2022
1406:2019
1378:2019
1350:2015
1319:2020
1287:ISBN
1239:2010
1208:2014
1183:2022
1162:ISBN
1109:ISSN
1042:ISBN
856:LOOP
838:and
823:and
811:and
782:and
674:and
654:and
612:goto
578:VHDL
572:XSLT
570:and
536:and
534:Lisp
511:Perl
469:Java
325:some
321:that
115:and
51:, a
2146:doi
2117:doi
1995:PMC
1987:doi
1939:PMC
1921:doi
1909:107
1864:doi
1860:358
1823:PMC
1807:doi
1744:doi
1740:142
1154:doi
1101:doi
1074:doi
1014:doi
830:In
584:TeX
568:SQL
491:C++
487:Ada
475:or
226:'s
151:):
147:or
139:In
106:In
63:or
39:In
2335::
2168:.
2142:43
2123:.
2113:42
2107:.
2070:.
2003:.
1993:.
1977:.
1973:.
1947:.
1937:.
1929:.
1919:.
1907:.
1903:.
1880:.
1872:.
1858:.
1854:.
1831:.
1821:.
1813:.
1805:.
1793:.
1789:.
1766:.
1758:.
1750:.
1738:.
1686:.
1652:.
1622:.
1593:.
1566:.
1469:.
1423:.
1395:.
1367:.
1340:.
1336:.
1309:.
1229:.
1225:.
1199:.
1170:,
1160:,
1152:,
1138:,
1115:.
1107:.
1097:37
1070:20
1068:.
1064:.
1008:.
940:mn
558:m4
517:,
513:,
509:,
505:,
501:,
497:,
493:,
489:,
477:C#
471:,
457:,
290:Z4
278:Z3
180:.)
119:.
2292:"
2285:"
2278:"
2271:"
2264:"
2200:e
2193:t
2186:v
2172:.
2152:.
2148::
2131:.
2119::
2095:.
2076:.
2061:.
2023:.
1989::
1979:2
1955:.
1923::
1915::
1888:.
1866::
1839:.
1809::
1801::
1795:8
1774:.
1746::
1697:.
1671:.
1634:.
1607:.
1574:.
1537:.
1515:.
1482:.
1434:.
1408:.
1380:.
1352:.
1321:.
1295:.
1241:.
1210:.
1156::
1146::
1123:.
1103::
1080:.
1076::
1020:.
1016::
1010:4
938:s
574:.
560:.
550:.
540:.
521:.
519:R
479:.
461:.
455:C
166:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.