In computer science, Turing completeness is a classification for a system of rules that manipulate data. It is named after computer scientist Alan Turing, inventor of the Turing machine.
For instance, programming languages and CPU instruction sets are examples of formal rule systems that access and modify data. If the rules can simulate Turing’s hypothetical computing machine, the rules are said to be “Turing complete.” A Turing-complete system can be proven mathematically to be capable of performing any possible calculation or computer program.
An example of a Turing complete system is lambda calculus that was developed by Alonzo Church, Alan Turing’s professor.
Examples of Turing complete systems
- Many procedural programming languages, including C and Pascal.
- Most object-oriented programming languages, such as Java and C++.
- Logic programming languages, such as Prolog.
- Many finite automata systems, such as Conway’s Game of Life.
Computer Science, Lambda calculus, Programming terms
