What Is Meant By Turing Completeness

First, we should start off by explaining what a Turing Machine is. A Turing Machine is a theoretical machine that manipulates symbols on a tape. This machine is simple but easily adaptable. It is able to simulate the logic of any algorithm and is especially useful at explaining how a CPU functions. The machine is named after Alan Turing, who was one of the most significant computer scientists and mathematicians of the early to mid 1900’s. He developed this device as a thought experiment with the purpose of representing a computing machine. It wasn’t meant to be an actual, practical computing device.

In order for a programming language, instruction set, or similar set of data-manipulation rules to be Turing complete it must be able to fully simulate a Turing machine. The rules that follow in sequence on data must be able to produce the result of any calculation. At a minimum, to be Turing complete, the rules must contain conditional branching and the ability to change memory.

It can be proven that something is Turing complete by showing that the rules can simulate the most primitive computer, because even the simplest computer can simulate the most complicated computer.

This is a very basic answer, but this should provide a good overview to get started learning about what it means to be Turing complete. Check out the resources below for additional information.

Additional Resources

Written on August 25, 2010