Turing Machine

Definition

A turing machine is a theoretical computing device which has been used extensively in analyzing computing problems such as tractability and complexity theory. Its basic components are an infinite length of tape and a head which operates on the tape. The tape is divided into segments, each of which can hold a single character which is an element of a predefined, finite set of characters called the 'tape alphabet'. The head is always in one 'state' which is an element in a predefined, finite set of states. The head is also always in a single location on the tape (i.e. there is one character on the tape at which the head is located). In a single computing step the head reads the character from the tape, switches its state based on the character and its current state, and steps to an adjacent character either directly to the left or directly to the right of the current location, again based on the state and character it read.

One reduction which has been proven to place no limitations on the turing machine is limiting the tape alphabet to two characters; a turing machine with a binary alphabet can simulate any turing machine with an alphabet of any size. Therefore, turing machines are usually defined and studied using only the binary alphabet consisting of 1 and 0.

Turing Completeness

A device that can simulate any Turing Machine is called Turing complete. The device does not necessarily have to be intentionally designed to compute or be a computer; if a device, piece of software or even an abstract concept meets the criteria it is Turing complete.

Even software that is only used as a teaching tool or exist only as a concept, not as an implementation (such as Donald Knuth's MMIX can be considered "Turing complete," in a completely abstract sense.

The name "Turing machine" and the concept known as "Turing completeness" are both derived from noted mathematician and computer scientist Alan Turing.