Editing Turing completeness (section)

==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