ITEC 420 - Section 3.1 - Turing Machines

Turing Machine: Introduction

• Turing Machines can recognize all computable languages
• We will leave the notion of computable language as intuitive
• We will see well-defined languages that are NOT computable with a TM (or in any other known way)
• We will see that all known ways of computing have the same power as the TM (or less)


• Implementation: TM = FSM + Tape!

A Turing Machine's Tape

• Tape is infinite (in one direction)


• Tape is initialized with input at left end
• Rest of tape has blanks
• Blank not in input alphabet


• Tape has R/W head:
• Reads and writes the symbol under the head at each transition
• Moves one symbol left or right at each transition
• Attempts to move past left end of tape leave tape at left end of tape
• Machine can NOT tell where on the tape the head is

Example Turing Machine

• A = {w#w | w ∈ {0,1}*}
• Algorithm intution: ... (p 139)

Turing Machine: Halting a Computation

• Computation can do one of three things:
1. End (immediately) by entering a special Accept state
2. End (immediately) by entering a special Reject state
3. Continue forever (ie never enter Accept or Reject state)


• For comparison, consider the halting conditions for these machines:
• DFA
• NFA
• PDA

Turing Machine Accepts a String

• Machine M accepts string w if w takes M to the Accept State of M

Turing Machines: More Examples

• A = {w#w | w ∈ {0,1}*}
• Formal specification of machine: (Example 3.9, p. 145)


• B = {ww | w ∈ {0,1}*}
• Algorithm: How would we find the center of the string? ...


• C = {aⁿbⁿcⁿ | n ≥ 0}
• Algorithm: ...


• D = {0²ⁿ | n ≥ 0} (Example 3.7, p 143, 144)

Formal Definition of a TM

• Must define seven items:
1. Q is the set of state
2. Σ is the input alphabet (does not include the blank symbol)
3. Γ is the tape alphabet, blank ∈ Γ and Σ ⊆ Γ
4. δ: (state, tape symbol) → (state, tape symbol, L/R)
5. Start state
6. Accept state
7. Reject state (different from start state)


• Transition function: δ(q,b) → (r,c,D) means the machine is in state q and the tape head is over a b. The machine then writes an c onto the tape (erasing the b), goes into state r, and moves direction D on the tape.
• Shorthand notation: a → D means to read and write and a and to move direction D


• Deterministic or non-deterministic?

Configuration of a TM

• Show tape head position by writing current state to left of symbol it is over:


• Example: 1011q₇01111
• Tape contents are 101101111, tape head is over rightmost 0, and machine is in state q₇
• tape head is over rightmost 0, and machine is instate q₇
• machine is in state q₇


• Accepting/Rejecting Configuration
• Machine halts when machine enters Accept or Reject State!
• Tape head can be anywhere!

TM Computation: Formal Definition

• A computation is a sequence of configurations of machine M in which
• First configuration in the sequence has M in the start state with M's head at the left of the tape


• Each step in the sequence moves M to the next configuration with a single read, a single write, and a single move

TM Accepts a String: Formal Definition

• Machine M accepts string w iff there is a computation that
• Starts with the start configuration of w on M (ie w written on left end of tape and R/W head at left end)
• M takes each configuration in the computation to the next configuration
• The computation ends in an accepting configuration (ie in the accept state)


• No surprises here, but remember the head can be anywhere at the end of the computation

Recognizing a Language

• The language recognized by machine M is the collection of strings accepted by M

A Turing Recognizable Language

• A language that is recognized by a machine is called a Turing Recognizable language


• Later we'll see that there is some subtlety here


• For now, remember that language L is TR, if there is a TM M for which all strings in L put M in its accept state.


• So, how do we prove that a language is TR?


• Question: What about strings that are not in L?