Turing Machine Definition

Definition of a Turing Machine

We start with an informal description of a Turing Machine. Such a machine consists of the following:

1. There are k tapes , for some fixed k ≥ 1. Each tape is divided into cells, and is infinite both to the left and to the right. Each cell stores a symbol belonging to a finite set Γ , which is called the tape alphabet. The tape alphabet contains the blank symbol Δ. If a cell contains Δ , then this means that the cell is actually empty.

   

2. Each tape has  a tape head which can move along the tape, one cell per move. It can also read the cell it currently scans and replace the symbol in this cell by another symbol.
3. There is the state control, which can be any in any one of a finite number of states. The finite set of states is denoted by Q. The set Q contains three special states: a start state, an accept state, and a reject state.

The Turing machine performs a sequence of computation steps. In one such steps, it does the following:

1. Immediately before the computation step, the Turing machine is in a state r of Q, and each of the k tape heads is on a certain cell.
2. Depending on the current state r and the k symbols that are read by the tape heads, 
   1. the Turing machine switches to a state r’ of Q (which may be equal to r)
   2. each tape head writes a symbol of Γ in the cell it is currently scanning (this symbol may be equal to the symbol currently stored in the cell), and
   3. each tape head either moves one cell to the left, moves one cell to the right, or stays at the current cell.

We now give a format definition of a deterministic Turing machine.

Definition: A deterministic Turing machine is a 7-tuple

M = (Σ, Γ, Q, δ, q, q_accept, q_reject),

where

1. Σ is a finite set, called the input alphabet; the blank symbol Δ is not contained in Σ, 
2. Γ is a finite set, called the tape alphabet; this alphabet contains the blank symbol Δ, and Σ ⊆ Γ,
3. Q is a finite set, whose elements are called states, 
4. q is an element of Q; it is called the state state,
5. q_accept is an element of Q; it is called the accept state,
6. q_reject is an element of Q; it is called the reject state,
7. δ is called the transition function, which is a function

δ: Q x Γ^k x {L, R, N}^k.

The transition function δ is basically the “program” of the Turing machine. This function tells us what the machine can do in “one computation step”: Let r ∈ Q, and let a₁,a₂,…..,a_k ∈ Γ. Furthermore, let r’ ∈ Q, a’₁,a’₂,a’₃,….,a’_k ∈ Γ, and σ₁, σ₂,σ₃,….,σ_k ∈ {L,R,N} be such that

δ(r,a₁,a₂,…..,a_k ) = (r’, a’₁,a’₂,a’₃,….,a’_k ,σ₁, σ₂,σ₃,….,σ_k ).

This transition means that if

• the Turing machine is in state r, and
• the head of the i-th tape reads the symbol a_i, 1 ≤ i ≤ k,

then

• the Turing machine switches to state r’,
• the head of the i-th tape replaces the scanned symbol a_i by the symbol a’_i, 1 ≤ i ≤ k, and 
• the head of the i-th tape moves according to σ_i, 1 ≤ i ≤ k: if σ_i = L, then the tape head moves one cell to the left; if σ_i = N, then the tape head does not move.

We will write the computation step in the form of the instruction 

ra₁a₂…..a_k → r’a’₁a’₂a’₃….a’_kσ₁σ₂σ₃….σ_k

We now specify the computation of the Turing Machine

M = (Σ, Γ, Q, δ, q, q_accept, q_reject).

Like us: Theory of Computation