Editing Turing completeness (section)

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