Turing machine

The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

Definition

Informal description

A Turing machine is a pushdown automaton made more powerful by relaxing the last-in-first-out requirement of its stack. (Interestingly, this seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a model for the computational capabilities of all modern computer software.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

More precisely, a Turing machine consists of:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol.
• A head that can read and write symbols on the tape and move left and right.
• A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized.
• An action table (or transition function) that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt.

Note that every part of the machine is finite; it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Formal definition

One-tape Turing machine

More formally, a (one-tape) Turing machine is usually defined as a 6-tuple M=(Q, Gamma, s, b, F, delta), where

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• $Q$ is a finite set of states
• $Gamma$ is a finite set of the tape alphabet
• $s\; in\; Q$ is the initial state
• $b\; in\; Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
• $F\; subseteq\; Q$ is the set of final or accepting states
• $delta:\; Q\; imes\; Gamma\; ightarrow\; Q\; imes\; Gamma\; imes\; \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift.

Definitions in the literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, changing the set {L,R} to {L,R,S}, where S would allow the machine to stay on the same tape cell instead of moving left or right, does not increase the machine's computational power.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

k-tape Turing machine

A k-tape Turing machine can similarly be described as a 6-tuple M=(Q, Gamma, s, b, F, delta), where

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• $Q$ is a finite set of states
• $Gamma$ is a finite set of the tape alphabet
• $s\; in\; Q$ is the initial state
• $b\; in\; Gamma$ is the blank symbol
• $F\; subseteq\; Q$ is the set of final or accepting states
• $delta:\; Q\; imes\; Gamma^k\; ightarrow\; Q\; imes\; (Gamma\; imes\; \{L,R,S\})^k$ is a partial function called the transition function, where L is left shift, R is right shift, S is no shift.

Note that a k-tape Turing Machine is no more powerful than a standard Turing Machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~