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, Σ, Γ, δ, q₀, q_accept, q_reject> where Q, Σ, Γ are all finite sets, and:	A Turing Machine is a 7-tuple M = <Q, Σ, Γ, δ, q₀, #, F> where:	A Turing Machine is a 7-tuple M = <Q, Γ, b, Σ, δ, q₀, 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
q₀	q₀ ∈ Q is the start state	q₀ ∈ Q is the initial state	q₀ ∈ Q is the initial state
F, q_accept	q_accept ∈ 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.
q_reject	q_reject ∈ Q is the reject state, where q_reject ≠ q_accept	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 q_accept and q_reject.
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 q_accept, and no further transitions are allowed.
In the Sipser definition, δ is a function, and q_reject 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 q_n ∉ F.