Course contentsShow
← Computer Science
Lesson 1857 of 2,87242. Turing Machines and ComputabilityFree lesson

Formal Definition of a Turing Machine

Present the formal 7-tuple definition: (Q, Σ, Γ, δ, q₀, qaccept, qreject) with their roles and constraints.

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.