Back كمال تورنغ Arabic Цялостност по Тюринг Bulgarian Turing complet Catalan Turingovská úplnost Czech Turing-komplet Danish Turing-Vollständigkeit German Πληρότητα Τούρινγκ Greek Turing kompleteco Esperanto Turing completo Spanish تورینگ کامل Persian
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[1][2] (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.[a]
A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.[4] 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.[5][6]
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.[7][8]
- ^ Tom Stuart (2013). Understanding Computation: From Simple Machines to Impossible Programs. O'Reilly Media, Inc. p. 209. ISBN 978-1-4493-3011-8. Extract of page 209
- ^ Cristian S Calude (2024). To Halt Or Not To Halt? That Is The Question. World Scientific. p. 30. ISBN 978-981-12-3229-9. Extract of page 30
- ^ Michaelson, Greg (14 February 2020). "Programming Paradigms, Turing Completeness and Computational Thinking". The Art, Science, and Engineering of Programming. 4 (3). arXiv:2002.06178. doi:10.22152/programming-journal.org/2020/4/4.
- ^ Göktürk Üçoluk; Sinan Kalkan (2012). Introduction to Programming Concepts with Case Studies in Python (illustrated ed.). Springer Science & Business Media. p. 13. ISBN 978-3-7091-1343-1. Extract of page 13
- ^ Ben Goertzel (2013). The Structure of Intelligence: A New Mathematical Model of Mind (illustrated ed.). Springer Science & Business Media. p. 13. ISBN 978-1-4612-4336-6. Extract of page 13
- ^ Alan Garnham (2017). Artificial Intelligence: An Introduction. Routledge. p. 164. ISBN 978-1-351-33786-1. Extract of page 164
- ^ Torben Ægidius Mogensen (2022). Programming Language Design and Implementation. Springer Nature. p. 6. ISBN 978-3-031-11806-7. Extract of page 6
- ^ John R. Woodward (2003). "Modularity in Genetic Programming". In Conor Ryan (ed.). Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings, Volume 6 (illustrated ed.). Springer Science & Business Media. p. 258. doi:10.1007/3-540-36599-0_23. ISBN 978-3-540-00971-9. Extract of page 258
Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).