Turing complete en · ADJ
Pronunciation
- (US) audio
Meanings
-
(not-comparable) Equivalent in power to a universal Turing machine; equivalently, functionally complete.
All languages that are equivalent to Turing's specification are said to be Turing complete. Turing completeness is a surprisingly low bar. Many hand calculators can understand a Turing complete language. PDF (Portable Document Format), in which many documents on the Internet are available, is itself a Turing complete language.
2005, Ben Klemens, Math You Can't Use: Patents, Copyright, and Software, Brookings Institution Press, →ISBN, page 35:
Forms
| Spelling | Features | Labels | Source |
|---|---|---|---|
| Turing-complete | alternative | lexicographic |
Relateds
Turing machine · universal Turing machine · functionally complete · recursive function