Formal Definition of a Turing Machine
What you'll learn: You'll see the complete mathematical structure that formally defines every Turing Machine using a 7-tuple specification.
The Seven Components
After exploring Turing Machines informally, we now formalize them precisely. A Turing Machine is defined as a 7-tuple:
M = (Q, Σ, Γ, δ, q₀, qaccept, qreject)
Let's break down each component:
Q — Finite Set of States
The collection of all possible control states the machine can be in.
Σ — Input Alphabet
The finite set of symbols that can appear in the input string (does not include the blank symbol).
Γ — Tape Alphabet
The finite set of symbols that can appear on the tape. Must satisfy: Σ ⊆ Γ, and the blank symbol ⊔ ∈ Γ but ⊔ ∉ Σ.
δ — Transition Function
The rules governing computation: δ: Q × Γ → Q × Γ × {L, R}
This means: given a current state and tape symbol, δ specifies the next state, symbol to write, and direction to move (Left or Right).
q₀ — Start State
The unique state where computation begins (q₀ ∈ Q).
qaccept — Accept State
The unique state indicating acceptance (qaccept ∈ Q). Entering this state means the input is accepted.
qreject — Reject State
The unique state indicating rejection (qreject ∈ Q, qreject ≠ qaccept). The machine halts and rejects when entering this state.
Critical Constraints
- qaccept and qreject are halting states — the machine stops upon reaching them
- δ is not defined for qaccept or qreject (no transitions out)
- The machine may also halt by having no defined transition for a (state, symbol) pair
Key Takeaway: A Turing Machine is precisely specified by seven components: states, two alphabets, a transition function, and three distinguished states — together forming the mathematical foundation for defining computation itself.