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:

• Although each defines a Turing Machine as a 7-tuple, Sipser omits “blank” and F, but includes qaccept and qreject.
• Whether stated or not, all sets are finite.
• For any meaningful definition, Q, Σ, and Γ must all be nonempty.
• F is probably nonempty, but it's easy to envision a Turing Machine that accepts no strings.
• The transition function δ can be specified as a set of 5-tuples of the form R(current state, symbol read, symbol written, direction, next state).

# More important points:

• Blanks are special.
• The tape contains a finite, contiguous number of non-blank characters, but an infinite number of blank characters.
• If blanks were allowed in the “input” data, it would be impossible to know when the TM reaches the end of the data.
• In the Sipser definition, a Turing Machine does nothing if told to move left onto a blank (that is, to the left of the input).
• In the Sipser definition, F consists of the single state qaccept, and no further transitions are allowed.
• In the Sipser definition, δ is a function, and qreject acts as an error state. For the others, δ is a partial function, and the input is rejected if there is no transition from the current state qn ∉ F.