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_{0}, q_{accept}, q_{reject}> where Q, Σ, Γ are all finite sets, and: |
A Turing Machine is a 7-tuple M = <Q, Σ, Γ, δ, q_{0}, #, F> where: |
A Turing Machine is a 7-tuple M = <Q, Γ, b, Σ, δ, q_{0}, 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_{0} |
q_{0 } ∈ Q is the start state |
q_{0 } ∈ Q is the initial state |
q_{0 } ∈ 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) |

- 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)

- 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.