Turing completeness

Updated: 10/17/2017 by Computer Hope
Turing completeness

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 (central processing unit) 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

Computer Science, Lambda calculus, Programming terms