<< Back

Turing Completeness

"A problem is said to be Turing-complete if it can only be solved by a Turing machine or any system that is TuringEquivalent. Often programming languages that are TuringEquivalent are said to be TuringComplete. A given programming language is said to be Turing-complete if it can be shown that it is computationally equivalent to a Turing machine." In essence, a problem that can be solved on a Turing machine with a limited amount of resources such as time, and tape, can also be solved with the other language using a limited amount of its resources . One may prove that a programming language is Turing-complete by providing a process for translating another given Turing machine program into an equivalent program in the language. Alternately, one can provide a scheme used to translate another language, one that has already been proven to be Turing-complete ("Turing Complete").

According to Wolfram MathWorld, "A Turing machine is a theoretical computing machine invented by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine consists of a line of cells known as a "tape" that can be moved back and forth, an active element known as the "head" that possesses a property known as "state" and that can change the property known as "color" of the active cell underneath it, and a set of instructions for how the head should modify the active cell and move the tape. At each step, the machine may modify the color of the active cell, change the state of the head, and then move the tape one unit to the left or right" ("Turing Machine.").

Therefore, a Turing Complete system is a system where a program can be written to solve a particular problem or find a particular answer. So, in principle Turing Complete can be used to solve any computational problem, although not always in practice. For example, C may not be a Turing complete language because its pointers' size is limited, thereby, also limiting the memory required to perform infinite computable procedures.


"Turing Complete." Turing Complete. N.p., n.d. Web. 09 Sept. 2012.
Sept. 2012. http://c2.com/cgi/wiki?TuringComplete.

"Turing Machine." -- from Wolfram MathWorld. N.p., n.d. Web. 09 Sept. 2012.
Sept. 2012. http://mathworld.wolfram.com/TuringMachine.html.