Language Turing Completeness
Back to Languages
A programming language is turing complete if it is in the same computational class as a Turing Machine.
In general, for an imperative language to be Turing-complete, it needs:
- A form of conditional repetition or conditional jump (e.g., while, if+goto)
- A way to read and write some form of storage (e.g., variables, tape)
For a lambda-calculus–based functional language to be TC, it needs:
- The ability to abstract functions over arguments (e.g., lambda abstraction, quotation)
- The ability to apply functions to arguments (e.g., reduction)