What is a Turing machine; its operation

Definition

A Turing machine (TM) is a mathematical model of a general-purpose computer, proposed by Alan Turing (1936). It consists of a finite control, an infinite tape divided into cells, and a read/write head.

Formally, M = (Q, Σ, Γ, δ, q0, ⊔, F), where

• Q is a finite set of states, q0 ∈ Q the start state, F ⊆ Q the final (accepting) states,
• Σ is the input alphabet (not containing the blank), Γ ⊇ Σ ∪ {⊔} the tape alphabet, ⊔ the blank,
• δ : Q × Γ → Q × Γ × {L, R, S} is the transition function (partial).

         ┌───────────────┐
         │ finite control│  state q
         └───────┬───────┘
                 │ head
     ... ⊔ │ a │ b │ a │ ⊔ │ ⊔ ...   infinite tape

Operation

1. The input string w is written on the tape, the rest of the tape is blank, the head is on the leftmost symbol, and the state is q0.
2. In each step, the machine reads the symbol under the head. If δ(q, a) = (p, b, D), it writes b over a, moves the head one cell in direction D (L, R or stay), and changes state to p.
3. This repeats. If no move is defined, the machine halts.
4. w is accepted if M halts in a state of F. It is rejected if M halts in a non-final state; on some inputs M may also run forever (loop).

The language accepted is L(M) = { w : q0 w ⊢* u p v with p ∈ F }.

Example

For δ(q0, 1) = (q0, 1, R) and δ(q0, ⊔) = (qa, ⊔, S): the machine scans a string of 1's from left to right and accepts at the first blank, so it accepts 1*.

Turing machines accept exactly the recursively enumerable languages and compute the partial recursive functions. By the Church–Turing thesis, they capture everything an algorithm can compute.