CIT 596 Definitions of Turing Machines
Spring 2012, David Matuszek

The definition of a “Turing Machine” may differ slightly from one source to another. Here are three definitions:

  Michael Sipser Peter Linz Wikipedia
Turing Machine A Turing Machine is a 7-tuple M = <Q, Σ, Γ, δ, q0, qaccept, qreject> where Q, Σ, Γ are all finite sets, and: A Turing Machine is a 7-tuple M = <Q, Σ, Γ, δ, q0, #, F> where: A Turing Machine is a 7-tuple M = <Q, Γ, b, Σ, δ, q0, F> where:
Q Q is the set of states Q is a set of states Q is a finite, non-empty set of states
Γ Γ is the tape alphabet, where ⌊⌋ ∈ Γ and Σ ⊆ Γ Γ is a finite set of symbols, the tape alphabet, Γ is a finite, non-empty set of the tape alphabet/symbols
b or # (not part of the 7-tuple) # ∈ Γ is a symbol called “blank” b ∈ Γ is the blank symbol
Σ Σ is the input alphabet not containing the special blank symbol ⌊⌋ Σ is a finite set of symbols, the input alphabet Σ ⊆ Γ - {b} is the set of input symbols
q0 q0 ∈ Q is the start state q0 ∈ Q is the initial state q0 ∈ Q is the initial state
F, qaccept qaccept ∈ Q is the accept state F ⊆ Q is a set of final states F ⊆ Q is the set of final (accepting) states
δ δ: Q × Γ → Q × Γ × {L, R} is the transition function δ: Q × Γ → Q × Γ × {L, R} is the partial transition function δ: Q - F × Γ → Q - F × Γ × {L, R} is a partial function called the transition function, where L is left shift, R is right shift.
qreject qreject ∈ Q is the reject state, where qreject ≠ qaccept Equivalent to Q - F (not part of the 7-tuple) Equivalent to Q - F (not part of the 7-tuple)

Minor points:

More important points: