Turing completeness

Updated: 09/15/2017 by Computer Hope

turing completenessIn 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 be used to 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. Other examples of Turing complete systems include:

Computer Science, Lambda calculus, Programming terms