Editing Turing completeness

{{Short description|Ability of a computing system to simulate Turing machines}}
{{For|the usage of this term in the theory of relative computability by oracle machines|Turing reduction}}
{{Use dmy dates|date=November 2017}}

In [[computability theory]], a system of data-manipulation rules (such as a [[model of computation]], a computer's [[instruction set]], a [[programming language]], or a [[cellular automaton]]) is said to be '''Turing-complete''' or '''computationally universal''' if it can be used to simulate any [[Turing machine]]<ref>{{cite book |title=Understanding Computation: From Simple Machines to Impossible Programs |author1=Tom Stuart |edition= |publisher=O'Reilly Media, Inc. |year=2013 |isbn=978-1-4493-3011-8 |page=209 |url=https://books.google.com/books?id=TN7UAZTKqccC}} [https://books.google.com/books?id=TN7UAZTKqccC&pg=PA209 Extract of page 209]</ref><ref>{{cite book |title=To Halt Or Not To Halt? That Is The Question |author1=Cristian S Calude |edition= |publisher=World Scientific |year=2024 |isbn=978-981-12-3229-9 |page=30 |url=https://books.google.com/books?id=-u4GEQAAQBAJ}} [https://books.google.com/books?id=-u4GEQAAQBAJ&pg=PA30 Extract of page 30]</ref> (devised by English mathematician and computer scientist [[Alan Turing]]). 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.{{efn|Arguably,
T[uring] C[omplete] 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, overarching programming methodologies.<ref>{{cite journal |last1=Michaelson |first1=Greg |title=Programming Paradigms, Turing Completeness and Computational Thinking |journal=The Art, Science, and Engineering of Programming |date=14 February 2020 |volume=4 |issue=3 |doi=10.22152/programming-journal.org/2020/4/4|arxiv=2002.06178 }}</ref>}}

A related concept is that of '''Turing equivalence'''{{snd}} two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.<ref>{{cite book |title=Introduction to Programming Concepts with Case Studies in Python |author1=Göktürk Üçoluk |author2=Sinan Kalkan |edition=illustrated |publisher=Springer Science & Business Media |year=2012 |isbn=978-3-7091-1343-1 |page=13 |url=https://books.google.com/books?id=qHL5ah1GLoUC}} [https://books.google.com/books?id=qHL5ah1GLoUC&pg=PA13 Extract of page 13]</ref> The [[Church–Turing thesis]] conjectures that any function whose values can be computed by an [[algorithm]] 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 [[universal Turing machine]] can be used to simulate any Turing machine and by extension the purely computational aspects of any possible real-world computer.<ref>{{cite book |title=The Structure of Intelligence: A New Mathematical Model of Mind |author1=Ben Goertzel |edition=illustrated |publisher=Springer Science & Business Media |year=2013 |isbn=978-1-4612-4336-6 |page=13 |url=https://books.google.com/books?id=IUwOBwAAQBAJ}} [https://books.google.com/books?id=IUwOBwAAQBAJ&pg=PA13 Extract of page 13]</ref><ref>{{cite book |title=Artificial Intelligence: An Introduction |author1=Alan Garnham |edition= |publisher=Routledge |year=2017 |isbn=978-1-351-33786-1 |page=164 |url=https://books.google.com/books?id=qFI8DwAAQBAJ}} [https://books.google.com/books?id=qFI8DwAAQBAJ&pg=PT164 Extract of page 164]</ref>

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.<ref>{{cite book |title=Programming Language Design and Implementation |author1=Torben Ægidius Mogensen |edition= |publisher=Springer Nature |year=2022 |isbn=978-3-031-11806-7 |page=6 |url=https://books.google.com/books?id=pIedEAAAQBAJ}} [https://books.google.com/books?id=pIedEAAAQBAJ&pg=PR6 Extract of page 6]</ref><ref>{{cite conference |title=Modularity in Genetic Programming |author=John R. Woodward |doi=10.1007/3-540-36599-0_23 |book-title=Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings, Volume 6 |editor1=Conor Ryan |edition=illustrated |publisher=Springer Science & Business Media |year=2003 |isbn=978-3-540-00971-9 |page=258 |url=https://link.springer.com/book/10.1007/3-540-36599-0}} [https://books.google.com/books?id=JwRsdTav4NUC&pg=PA258 Extract of page 258]</ref>

==Non-mathematical usage==
In [[colloquial]] 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 practical concepts of computing [[virtualization]] and [[emulator|emulation]].{{cn|date=June 2022}}

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 [[linear bounded automaton]] complete.  In contrast, the abstraction of a [[universal computer]] is defined as a device with a Turing-complete instruction set, infinite memory, and infinite available time.{{cn|date=April 2024}}

==Formal definitions==
In [[computability theory]], several closely related terms are used to describe the computational power of a computational system (such as an [[abstract machine]] or [[programming language]]):

;Turing completeness
: A computational system that can compute every Turing-[[computable function]] is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a [[universal Turing machine]].
;Turing equivalence
: 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 [[Turing machine]]s. 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 [[Church–Turing thesis]].{{Citation needed|date=March 2021}})
;(Computational) universality
: 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 universal" is sometimes used to distinguish a system (e.g. a [[cellular automaton]]) whose universality is achieved only by modifying the standard definition of [[Turing machine]] so as to include input streams with infinitely many 1s.

==History==
Turing completeness is significant in that every real-world design for a computing device can be simulated by a [[universal Turing machine]]. The [[Church–Turing thesis]] states that this is a law of mathematics{{snd}} that a universal Turing machine can, in principle, perform any calculation that any other programmable [[computer]] can. This says nothing about the effort needed to write the [[computer program|program]], 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.

[[Charles Babbage]]'s [[analytical engine]] (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.{{citation needed|date=December 2021}} 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.

In the late 19th century, [[Leopold Kronecker]] formulated notions of computability, defining [[primitive recursive function]]s. 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, [[David Hilbert]] 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 [[Kurt Gödel]] in 1930 to be enough to produce every theorem.

The actual notion of computation was isolated soon after, starting with [[Gödel's incompleteness theorem]]. 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 {{lang|de|[[Entscheidungsproblem]]}} (decision problem) was unsolvable,<ref>{{ Citation | last = Hodges | first = Andrew | author-link = Andrew Hodges | orig-year = 1983 | year = 1992 | title = Alan Turing: The Enigma |location = London | publisher=Burnett Books | page = 111 | isbn = 0-04-510060-8 | title-link = Alan Turing: The Enigma }}</ref> thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on [[general recursive function]]s, 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.

In 1941 [[Konrad Zuse]] completed the [[Z3 (computer)|Z3]] 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, 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.<ref>{{cite journal |first=Raul |last=Rojas |title=How to make Zuse's Z3 a universal computer |journal=Annals of the History of Computing |volume=20 |issue=3 |pages=51–54 |year=1998 |doi=10.1109/85.707574  |url=https://www.researchgate.net/publication/3330654}}</ref>

The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the [[ENIAC]] in 1946. Zuse's [[Z4 (computer)|Z4]] computer was operational in 1945, but it did not support conditional branching until 1950.<ref>{{Cite journal|last=Rojas|first=Raúl|date=2014-02-01|title=Konrad Zuse und der bedingte Sprung|trans-title=Konrad Zuse and the conditional jump|journal=Informatik-Spektrum|language=de|volume=37|issue=1|pages=50–53|doi=10.1007/s00287-013-0717-9|s2cid=1086397|issn=0170-6012}}</ref>

==Computability theory==
[[Computability theory]] uses [[Model of computation|models of computation]] to analyze problems and determine whether they are [[Computability|computable]] 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.

The classic example is the [[halting problem]]: create an algorithm that takes as input a program in some Turing-complete language and some data to be fed to ''that'' 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 ''some'' 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.

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.

One can instead limit a program to executing only for a fixed period of time ([[Timeout (computing)|timeout]]) 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 [[Cantor's diagonal argument]] on all computable functions in that language.

==Turing oracles==
{{main article|Oracle machine}}

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 [[halting problem]] or some other Turing-undecidable problem. Such an infinite tape of data is called a [[Turing oracle]]. Even a Turing oracle with random data is not computable ([[Almost surely|with probability 1]]), 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.

==Digital physics==
{{See also|Church–Turing thesis#Philosophical implications}}
All known laws of physics have consequences that are computable by a series of approximations on a digital computer. A hypothesis called [[digital physics]] states that this is no accident because the [[universe]] 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.<ref>{{Citation |last=Schmidhuber |first=Jürgen |title=A computer scientist's view of life, the universe, and everything |date=1997 |url=https://doi.org/10.1007/BFb0052088 |work=Foundations of Computer Science: Potential — Theory — Cognition |series=Lecture Notes in Computer Science |volume=1337 |pages=201–208 |editor-last=Freksa |editor-first=Christian |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/bfb0052088 |isbn=978-3-540-69640-7 |s2cid=17830241 |access-date=2022-05-23 |editor2-last=Jantzen |editor2-first=Matthias |editor3-last=Valk |editor3-first=Rüdiger|arxiv=quant-ph/9904050 }}</ref>

==Examples==<!-- Please respect alphabetical order -->
The computational systems (algebras, calculi) that are discussed as Turing-complete systems are those intended for studying [[theoretical computer science]]. 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:
* [[Automata theory]]
* [[Formal grammar]] (language generators)
* [[Formal language]] (language recognizers)
* [[Lambda calculus]]
* [[Post–Turing machine]]s
* [[Process calculus]]

Most [[programming language]]s (their abstract models, maybe with some particular constructs that assume finite memory omitted), conventional and unconventional, are Turing-complete. This includes:
* All general-purpose languages in wide use.
** [[Procedural programming]] languages such as [[C (programming language)|C]], [[Pascal (programming language)|Pascal]].
** [[Object-oriented programming language|Object-oriented]] languages such as [[Java (programming language)|Java]], [[Smalltalk]] or [[C Sharp (programming language)|C#]].
** [[Multi-paradigm programming language|Multi-paradigm]] languages such as [[Ada (programming language)|Ada]], [[C++]], [[Common Lisp]], [[Fortran]], [[JavaScript]], [[Object Pascal]], [[Perl]], [[Python (programming language)|Python]], [[R (programming language)|R]].
* Most languages using less common paradigms:
** [[Functional programming|Functional]] languages such as [[Lisp (programming language)|Lisp]] and [[Haskell (programming language)|Haskell]].
** [[Logic programming]] languages such as [[Prolog]].
** [[General-purpose macro processor]] such as [[m4 (computer language)|m4]].
** [[Declarative programming|Declarative]] languages such as [[SQL]] and [[XSLT]].<ref>{{cite web |author1=Dfetter |author2=Breinbaas |url=https://wiki.postgresql.org/index.php?title=Cyclic_Tag_System&oldid=15106 |title=Cyclic Tag System |website=PostgreSQL wiki |date=8 August 2011 |access-date=2014-09-10}}</ref><ref>{{cite web |url=https://unidex.com/turing/utm.htm |title=Universal Turing Machine in XSLT |website=B2B Integration Solutions from Unidex |first=Bob |last=Lyons |date=30 March 2001 |access-date=2010-07-05 |url-status=live |archive-date=17 July 2011 |archive-url=https://web.archive.org/web/20110717162708/https://unidex.com/turing/utm.htm |df=dmy-all }}</ref>
** [[VHDL]] and other hardware description languages.
** [[TeX]], a typesetting system.
** [[Esoteric programming language]]s, a form of [[mathematical recreation]] in which programmers work out how to achieve basic programming constructs in an extremely difficult but mathematically Turing-equivalent language.

Some [[rewrite system]]s are Turing-complete.

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 [[goto]] statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use [[recursion]]. Most programming languages are describing computations on [[von Neumann architecture]]s, which have memory (RAM and register) and a control unit. These two elements make this architecture Turing-complete. Even pure [[functional language]]s are Turing-complete.<ref>{{cite tech report |last1=Boyer |first1=Robert S. |last2=Moore |first2=J. Strother |title=A Mechanical Proof of the Turing Completeness of Pure Lisp |number=37 |institution=Institute for Computing Science, University of Texas at Austin |date=May 1983 |url=https://cs.utexas.edu/users/boyer/ftp/ics-reports/cmp37.pdf |format=PDF |url-status=live |archive-date=22 September 2017 |archive-url=https://web.archive.org/web/20170922044624/https://cs.utexas.edu/users/boyer/ftp/ics-reports/cmp37.pdf |df=dmy-all }}</ref><ref>{{cite book |first1=Thomas |last1=Rauber |first2=Gudula |last2=Rünger |title=Parallel programming: for multicore and cluster systems |date=2013 |url=https://books.google.com/books?id=UbpAAAAAQBAJ |publisher=Springer |isbn=9783642378010 |edition=2nd}}</ref>

Turing completeness in declarative SQL is implemented through [[Hierarchical and recursive queries in SQL|recursive common table expressions]]. Unsurprisingly, procedural extensions to SQL ([[PLSQL]], 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.

The untyped [[lambda calculus]] is Turing-complete, but many typed lambda calculi, including [[System F]], are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.

[[Rule 110]] and [[Conway's Game of Life]], both [[cellular automaton|cellular automata]], are Turing-complete.

===Unintentional Turing completeness===
Some [[software]] and [[video games]] are Turing-complete by accident, i.e. not by design.<!--As a general rule, Arxiv documents are not accepted as sources, as they are [[WP:SELFPUBLISHED]]. Twitter user posts are generally no accepted sources either.-->

Software:

* [[Microsoft Excel]]<ref>{{Cite web|date=2020-12-03|title=Announcing LAMBDA: Turn Excel formulas into custom functions|url=https://techcommunity.microsoft.com/t5/excel-blog/announcing-lambda-turn-excel-formulas-into-custom-functions/ba-p/1925546|access-date=2020-12-08|website=TECHCOMMUNITY.MICROSOFT.COM|language=en}}</ref><!-- You might have seen the article on BoingBoing that says PowerPoint is Turing-complete. Maybe it is, but the BoingBoing article cites a YouTube presentation that was part of SIGBOVIK. SIGBOVIK is a *PARODY* conference. If something is presented in SIGBOVIK, that does not mean it's true, and might in fact mean that it's *NOT* true. If you want the article to say that Microsoft PowerPoint is Turing-complete, get a better source than something which ultimately points back to SIGBOVIK. -->

Games:
* ''[[Dwarf Fortress]]''<ref>{{cite web |url=https://themarysue.com/dwarf-fortress-turing-machine-computer/ |title=Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine |last1=Cedotal |first1=Andrew |date=16 April 2010 |website=The Mary Sue |access-date=2 June 2015 |url-status=live |archive-date=27 June 2015 |archive-url=https://web.archive.org/web/20150627102458/https://themarysue.com/dwarf-fortress-turing-machine-computer/ |df=dmy-all }}</ref>
* ''[[Cities: Skylines]]''<ref>{{cite web | url = https://kotaku.com/cities-skylines-map-becomes-a-poop-powered-calculator-1836398063  |title = Cities: Skylines Map Becomes A Poop-Powered Computer | first= Luke | last = Plunkett | date = July 16, 2019 | access-date = July 16, 2019 | work = [[Kotaku]] }}</ref>
* ''[[Opus Magnum (video game)|Opus Magnum]]''<ref>{{cite web |url=https://rockpapershotgun.com/2017/11/20/opus-magnum-player-makes-computer/ |title=Opus Magnum player makes an alchemical computer |first=Brendan |last=Caldwell |date=November 20, 2017 |access-date=September 23, 2019 |work=[[Rock Paper Shotgun]]}}</ref>
* ''[[Minecraft]]''<ref>{{Cite web |last=Crider |first=Michael |title=This 8-bit processor built in Minecraft can run its own games |url=https://pcworld.com/article/559794/8-bit-computer-processor-built-in-minecraft-can-run-its-own-games.html |access-date=2022-07-21 |website=PCWorld |language=en-US}}</ref>
* ''[[Magic: The Gathering]]''<ref>{{cite conference |last1=Churchill |first1=Alex |last2=Biderman |first2=Stella |last3=Herrick |first3=Austin |year=2020 |title=Magic: The Gathering Is Turing Complete |url=https://cs.emis.de/LIPIcs/volltexte/2020/12760/pdf/lipics-vol157-fun2021-complete_.pdf#page=169 |conference=10th International Conference on Fun with Algorithms}}</ref><ref>{{cite web |last=Ouellette |first=Jennifer |date=June 23, 2019 |title=It's possible to build a Turing machine within Magic: The Gathering |url=https://arstechnica.com/science/2019/06/its-possible-to-build-a-turing-machine-within-magic-the-gathering/ |access-date=March 12, 2023 |work=[[Ars Technica]]}}</ref>
* Infinite-grid [[Minesweeper (video game)|Minesweeper]]<ref>{{cite web |url=https://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf |title=Infinite versions of minesweeper are Turing complete |last1=Kaye |first1=Richard |date=31 May 2007 |url-status=dead |archive-url=https://web.archive.org/web/20160803180423/https://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf |archive-date=3 August 2016 |access-date=8 July 2016 }}</ref>

Social media:
* ''[[Habbo Hotel]]''<ref>{{cite web |url=https://twitter.com/Habbo/status/1325785673304043522 |title=Habbo's Twitter thread on the implementation of a Turing machine inside the game. |date=November 9, 2020 |access-date=November 11, 2020}}</ref>

Computational languages:
* [[Template (C++)|C++ templates]]<ref>{{Cite book |url=https://archive.org/details/effectivec55spec00meye |title=Effective C++ : 55 specific ways to improve your programs and designs |last=Meyers, Scott (Scott Douglas) |date=2005 |publisher=Addison-Wesley |isbn=0321334876 |edition=3rd |location=Upper Saddle River, NJ |oclc=60425273 |url-access=registration}}</ref>
* [[printf]] format string<ref>[https://ioccc.org/2020/carlini/index.html A 27th IOCCC Winner]<br>{{cite conference|url=https://dl.acm.org/doi/10.5555/2831143.2831154|title=Control-flow bending: on the effectiveness of control-flow integrity|first1=Nicolas|last1=Carlini|first2=Antonio|last2=Barresi|first3=Mathias|last3=Payer|first4=David|last4=Wagner|first5=Thomas R.|last5=Gross|book-title=Proceedings of the 24th USENIX Conference on Security Symposium|isbn=9781931971232|date=August 2015|pages=161–176}}</ref>
* [[TypeScript]]'s type system<ref>{{cite web|url=https://itnext.io/typescript-and-turing-completeness-ba8ded8f3de3|title=TypeScript and Turing Completeness|last=Dabler|first=Ryan|date=September 23, 2021|website=ITNEXT|publisher=LINKIT|access-date=November 12, 2022}}</ref>
* [[x86 assembly language|x86 assembly]]'s MOV instruction<ref>{{Cite web|last=Dolan|first=Stephen|title=mov is Turing-complete|url=https://stedolan.net/research/mov.pdf|url-status=dead|archive-url=https://web.archive.org/web/20210214020524/https://stedolan.net/research/mov.pdf|archive-date=2021-02-14|access-date=2019-05-09|website=stedolan.net}}</ref><ref>{{cite web |url=https://hackaday.com/2021/05/21/one-instruction-to-rule-them-all-c-compiler-emits-only-mov/ |title=One Instruction To Rule Them All: C Compiler Emits Only MOV |last=Williams |first=Al |publisher=[[Hackaday]] |date=2021-03-21 |accessdate=2023-10-23 }}</ref><ref>{{Citation |title=Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas | date=25 September 2015 |url=https://youtube.com/watch?v=R7EEoWg6Ekk |access-date=2022-11-05 |language=en}}</ref>

Biology:
* [[Chemical computer|Chemical reaction networks]]<ref name=":0">{{Cite journal|last1=Shah|first1=Shalin|last2=Wee|first2=Jasmine|last3=Song|first3=Tianqi|last4=Ceze|first4=Luis|last5=Strauss|first5=Karin|author5-link=Karin Strauss|last6=Chen|first6=Yuan-Jyue|last7=Reif|first7=John|date=2020-05-04|title=Using Strand Displacing Polymerase To Program Chemical Reaction Networks|journal=Journal of the American Chemical Society|volume=142|issue=21|pages=9587–9593|doi=10.1021/jacs.0c02240|pmid=32364723|s2cid=218504535|issn=0002-7863}}</ref><ref name=":1">{{Cite journal|last1=Chen|first1=Yuan-Jyue|last2=Dalchau|first2=Neil|last3=Srinivas|first3=Niranjan|last4=Phillips|first4=Andrew|last5=Cardelli|first5=Luca|last6=Soloveichik|first6=David|last7=Seelig|first7=Georg|date=October 2013|title=Programmable chemical controllers made from DNA|journal=Nature Nanotechnology|language=en|volume=8|issue=10|pages=755–762|doi=10.1038/nnano.2013.189|pmid=24077029|pmc=4150546|bibcode=2013NatNa...8..755C|issn=1748-3395}}</ref><ref name=":2">{{Cite journal|last1=Srinivas|first1=Niranjan|last2=Parkin|first2=James|last3=Seelig|first3=Georg|last4=Winfree|first4=Erik|last5=Soloveichik|first5=David|date=2017-12-15|title=Enzyme-free nucleic acid dynamical systems|journal=Science|language=en|volume=358|issue=6369|pages=eaal2052|doi=10.1126/science.aal2052|issn=0036-8075|pmid=29242317|doi-access=free}}</ref><ref name=":3">{{Cite journal|last1=Soloveichik|first1=David|last2=Seelig|first2=Georg|last3=Winfree|first3=Erik|date=2010-03-23|title=DNA as a universal substrate for chemical kinetics|journal=Proceedings of the National Academy of Sciences|language=en|volume=107|issue=12|pages=5393–5398|doi=10.1073/pnas.0909380107|issn=0027-8424|pmid=20203007|pmc=2851759|bibcode=2010PNAS..107.5393S|doi-access=free}}</ref> and [[DNA computing|enzyme-based DNA computers]]<ref>{{cite journal | last = Shapiro | first = Ehud | author-link = Ehud Shapiro | title = A Mechanical Turing Machine: Blueprint for a Biomolecular Computer | journal = Interface Focus | publisher = [[Weizmann Institute of Science]] | date = 1999-12-07 | volume = 2 | issue = 4 | pages = 497–503 | url = https://wisdom.weizmann.ac.il/~udi/DNA5/scripps_short/index.htm  | doi =  10.1098/rsfs.2011.0118| pmid = 22649583 | pmc = 3363030 | archive-url=https://web.archive.org/web/20090103224150/https://wisdom.weizmann.ac.il/~udi/DNA5/scripps_short/index.htm  |archive-date=2009-01-03 | access-date = 2009-08-13 }}</ref> have been shown to be Turing-equivalent

==Non-Turing-complete languages==
Many computational languages exist that are not Turing-complete. One such example is the set of [[regular language]]s, which are generated by [[regular expression]]s and which are recognized by [[finite-state machine|finite automata]]. A more powerful but still not Turing-complete extension of finite automata is the category of [[pushdown automaton|pushdown automata]] and [[context-free grammar]]s, which are commonly used to generate parse trees in an initial stage of program [[compiler|compiling]]. Further examples include some of the early versions of the pixel shader languages embedded in [[Direct3D]] and [[OpenGL]] extensions.{{Citation needed|date=December 2010}}

In [[total functional programming]] languages, such as [[Charity (programming language)|Charity]] and [[Epigram (programming language)|Epigram]], all functions are total and must terminate. Charity uses a type system and [[control flow|control constructs]] based on [[category theory]], whereas Epigram uses [[dependent type]]s. The [[LOOP (programming language)|LOOP]] language is designed so that it computes only the functions that are [[primitive recursive function|primitive recursive]]. All of these compute proper subsets of the total computable functions, since the full set of total computable functions is not [[recursively enumerable set|computably enumerable]]. Also, since all functions in these languages are total, algorithms for [[recursively enumerable set]]s cannot be written in these languages, in contrast with Turing machines.

Although (untyped) [[lambda calculus]] is Turing-complete, [[simply typed lambda calculus]] is not.

==See also==
{{cols|colwidth=20em}}
* [[AI-completeness]]
* [[Algorithmic information theory]]
* [[Chomsky hierarchy]]
* [[Church–Turing thesis]]
* [[Computability theory]]
* [[Inner loop]]
* [[Loop (computing)]]
* [[Machine that always halts]]
* [[Rice's theorem]]
* [[Smn theorem|''s<sub>mn</sub>'' theorem]]
* [[Structured program theorem]]
* [[Turing tarpit]]
* [[Virtualization]]
* [[Emulation (computing)]]
{{colend}}

==Footnotes==
{{notelist}}

==References==
{{Reflist}}

==Further reading==
{{Refbegin}}
* {{cite book |last1=Brainerd |first1=W. S. |author2-link=Lawrence Landweber |last2=Landweber |first2=L. H. |date=1974 |title=Theory of Computation |publisher=Wiley |isbn=0-471-09585-0 |url-access=registration |url=https://archive.org/details/theoryofcomputat00brai}}
* {{cite magazine |url=https://newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html |title=Simplest 'universal computer' wins student $25,000 |first=Jim |last=Giles |magazine=[[New Scientist]] |date=24 October 2007 }}
* {{cite book |editor-last=Herken |editor-first=Rolf |date=1995 |title=The Universal Turing Machine: A Half-Century Survey |publisher=Springer Verlag |isbn=3-211-82637-8}}
* {{Cite journal | last= Turing | first= A. M. |date=1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi= 10.1112/plms/s2-42.1.230 | s2cid= 73712 | url = https://www.abelard.org/turpap2/tp2-ie.asp <!-- | url = https://cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf --> }}
* {{Cite journal| last = Turing | first = A. M. |date=1938 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–546 | doi = 10.1112/plms/s2-43.6.544}}
{{Refend}}

==External links==
* {{cite web |url=https://c2.com/cgi/wiki?TuringComplete |title=Turing Complete |website=wiki.c2.com}}

{{Alan Turing}}

{{DEFAULTSORT:Turing Completeness}}
[[Category:Theory of computation]]
[[Category:Turing machine]]
[[Category:Programming language theory]]