What Is Turing Completeness?

Turing completeness is when a programming language is able to carry out the functions of a Turing machine. This is a concept for a very basic mechanical computer, sometimes described as the simplest machine that can be considered a computer. Virtually all programming languages in use today, and in theory, the computers that run them, have Turing completeness.

The concept of Turing completeness comes from Alan Turing, a British computer scientist whose work included deciphering coded messages during World War II. Among his work on computing was the development of a philosophy of what a computer could actually do. This included the concept that computers work simply by running algorithms. That is to say that they follow a fixed set of rules to process data and in turn solve problems. This means a computer does not "think" or make decisions like a person can.

To illustrate the concept, Turing described a hypothetical machine that he called an "a-machine," with the "a" standing for automatic; others later called it the Turing machine. The machine would process a reel of tape that could move back or forwards and contained a line of symbols. At any moment the machine could process one symbol and, if necessary, alter it. For the purposes of the concept, the reel of tape could be infinitely long, meaning the memory of the computer was not inherently limited. This is an analogy for the idea that once a computer has a set of instructions to follow, the amount of data it can apply those instructions to is subject only to physical limits.

Ironically, most computers today do not actually have Turing completeness. This is because they have limitations on the storage space available and thus the data they can process. They also have physical limitations, most notably that eventually they will wear out. It is actually the programming language that has Turing completeness. Because of this, a computer running such a program is not a Turing computer, but can be used to simulate one.

Turing completeness should not be confused with the Turing test. This was an experiment designed by Turing to see if computers can converse in natural language. The principle of the test is that if a human cannot tell the difference between a text-only conversation with the computer and another human, the computer passes the test. While some computers have passed the test when the range of conversation subjects is restricted, none have done so in unrestricted conversation.