BU CS 332 – Theory of Computation
Lecture 11:
• TM Variants
• Closure Properties
Mark Bun March 1, 2020
Reading: Sipser Ch 3.2
The Basic Turing Machine (TM)
Tape 𝑎𝑎𝑏𝑏𝑎𝑎𝑎𝑎 Finite
…
Input
control
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts when control reaches
“accept” or “reject” state
3/2/2020 CS332 – Theory of Computation 2
Example 0 → 0,𝑅𝑅 𝑞𝑞0
⊔ → ⊔, 𝑅𝑅
⊔→⊔,𝑅𝑅
𝑞𝑞1 0 → 0,𝑅𝑅 𝑞𝑞accept
𝑞𝑞reject
Formal Definition of a TM
A TM is a 7-tuple 𝑀𝑀 = (𝑄𝑄, Σ, Γ, 𝛿𝛿, 𝑞𝑞0, 𝑞𝑞accept, 𝑞𝑞reject) • 𝑄𝑄 is a finite set of states
• Σ is the input alphabet (does not include ⊔) • Γ is the tape alphabet (contains ⊔ and Σ)
• 𝛿𝛿 is the transition function
…more on this later • 𝑞𝑞 ∈𝑄𝑄isthestartstate
0
• 𝑞𝑞accept ∈ 𝑄𝑄 is the accept state
• 𝑞𝑞reject ∈ 𝑄𝑄 is the reject state (𝑞𝑞reject ≠ 𝑞𝑞accept)
3/2/2020 CS332 – Theory of Computation 4
𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑄𝑄 × Γ × {𝐿𝐿, 𝑅𝑅}
𝐿𝐿 means “move left” and 𝑅𝑅 means “move right”
TM Transition Function
𝛿𝛿 𝑝𝑝,𝑎𝑎 = (𝑞𝑞,𝑏𝑏,𝑅𝑅) means:
• Replace 𝑎𝑎 with 𝑏𝑏 in current cell
• Transition from state 𝑝𝑝 to state 𝑞𝑞 • Move tape head right
𝛿𝛿 𝑝𝑝,𝑎𝑎 = (𝑞𝑞,𝑏𝑏,𝐿𝐿) means:
• Replace 𝑎𝑎 with 𝑏𝑏 in current cell
• Transition from state 𝑝𝑝 to state 𝑞𝑞
• Move tape head left UNLESS we are at left end of tape, in
which case don’t move
3/2/2020 CS332 – Theory of Computation 5
Configuration of a TM
A string with captures the state of a TM together with the contents of the tape
1010111⊔
𝑞𝑞5
…
3/2/2020 CS332 – Theory of Computation
6
Configuration of a TM: Formally
A configuration is a string 𝑢𝑢𝑞𝑞𝑢𝑢 where 𝑞𝑞 ∈ 𝑄𝑄 and 𝑢𝑢, 𝑢𝑢 ∈ Γ∗ • Tape contents = 𝑢𝑢𝑢𝑢 (followed by blanks ⊔)
• Current state = 𝑞𝑞
• Tape head on first symbol of 𝑢𝑢
1010111⊔
𝑞𝑞5
…
3/2/2020 CS332 – Theory of Computation
7
How a TM Computes
Start configuration: 𝑞𝑞0𝑤𝑤
One step of computation: •𝑢𝑢𝑎𝑎𝑞𝑞𝑏𝑏𝑢𝑢yields𝑢𝑢𝑎𝑎𝑎𝑎𝑞𝑞𝑞𝑢𝑢if 𝛿𝛿 𝑞𝑞,𝑏𝑏 =(𝑞𝑞𝑞,𝑎𝑎,𝑅𝑅) •𝑢𝑢𝑎𝑎𝑞𝑞𝑏𝑏𝑢𝑢yields𝑢𝑢𝑞𝑞𝑞𝑎𝑎𝑎𝑎𝑢𝑢if 𝛿𝛿 𝑞𝑞,𝑏𝑏 =(𝑞𝑞𝑞,𝑎𝑎,𝐿𝐿) • 𝑞𝑞𝑏𝑏𝑢𝑢yields𝑞𝑞𝑞𝑎𝑎𝑢𝑢if 𝛿𝛿 𝑞𝑞,𝑏𝑏 =(𝑞𝑞𝑞,𝑎𝑎,𝐿𝐿)
Accepting configuration: 𝑞𝑞 = 𝑞𝑞accept Rejecting configuration: 𝑞𝑞 = 𝑞𝑞reject
3/2/2020 CS332 – Theory of Computation 8
How a TM Computes
𝑀𝑀 accepts input 𝑤𝑤 if there is a sequence of configurations 𝐶𝐶1,…,𝐶𝐶𝑘𝑘 suchthat:
• 𝐶𝐶1 = 𝑞𝑞0𝑤𝑤
• 𝐶𝐶𝑖𝑖 yields 𝐶𝐶𝑖𝑖+1 for every 𝑖𝑖
• 𝐶𝐶𝑘𝑘 is an accepting configuration
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞accept
•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞reject OR 𝑀𝑀 runs forever
3/2/2020 CS332 – Theory of Computation 9
Recognizers vs. Deciders
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞accept
•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞rejectOR 𝑀𝑀 runs forever
𝐴𝐴 is (Turing-)decidable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀
which halts on every input
•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞 accept
•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞reject
3/2/2020 CS332 – Theory of Computation 10
Back to Hilbert’s Tenth Problem
Computational Problem: Given a Diophantine equation, does it have a solution over the integers?
𝐿𝐿=
• 𝐿𝐿 is Turing-recognizable
• 𝐿𝐿 is not decidable (1949-70)
3/2/2020 CS332 – Theory of Computation 11
TM Variants
3/2/2020 CS332 – Theory of Computation 12
How Robust is the TM Model?
Does changing the model result in different languages being recognizable / decidable?
So far we’ve seen…
– We can require that FAs/PDAs have a single accept state
– (CFGs can always be put in Chomsky Normal Form)
– Adding nondeterminism does not change the languages recognized by finite automata
Turing machines have an astonishing level of robustness 3/2/2020 CS332 – Theory of Computation 13
Extensions that do not increase the power of the TM model
• TMs that are allowed to “stay put” instead of moving
left or right 𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑄𝑄 × Γ × 𝐿𝐿, 𝑅𝑅, 𝑆𝑆
Proof that TMs with “stay put” are no more powerful:
Simulation: Convert any TM 𝑀𝑀 with “stay put” into an equivalent TM 𝑀𝑀𝑞 without
Replace every “stay put” instruction in 𝑀𝑀 with a move right instruction, followed by a move left instruction in 𝑀𝑀’
3/2/2020 CS332 – Theory of Computation 14
Extensions that do not increase the power of
the TM model
• TMs with a 2-way infinite tape, unbounded left to right Input
Tape …𝑎𝑎𝑏𝑏𝑎𝑎 …
Proof that TMs with 2-way infinite tapes are no more
powerful:
Simulation: Convert any TM 𝑀𝑀 with 2-way infinite tape into
a 1-way infinite TM 𝑀𝑀𝑞 with a “two-track tape”
3/2/2020 CS332 – Theory of Computation 15
Formalizing the Simulation
𝑀𝑀′ = (𝑄𝑄′,Σ,Γ′,𝛿𝛿′,𝑞𝑞′,𝑞𝑞′ ,𝑞𝑞′ ) 0 accept reject
New tape alphabet: Γ′ = (Γ × Γ) ∪ {$} New state set: 𝑄𝑄′ = 𝑄𝑄 × {+,−}
(𝑞𝑞, −) means “𝑞𝑞, working on upper track”
(𝑞𝑞, +) means “𝑞𝑞, working on lower track” New transitions:
If𝛿𝛿 𝑝𝑝,𝑎𝑎 =(𝑞𝑞,𝑏𝑏,𝐿𝐿),let𝛿𝛿𝑞 𝑝𝑝,− , 𝑎𝑎 ,𝑎𝑎 =( 𝑞𝑞,− , 𝑏𝑏,𝑎𝑎 ,𝑅𝑅) −−++
Also need new transitions for moving right, lower track, hitting $, initializing input into 2-track format
3/2/2020 CS332 – Theory of Computation 16
TMs are equivalent to…
• TMs with “stay put”
• TMs with 2-way infinite tapes
• Multi-tape TMs
• Nondeterministic TMs
• Random access TMs
• Enumerators
• Finite automata with access to an unbounded queue = 2- stack PDAs
• Primitive recursive functions
• Cellular automata …
3/2/2020 CS332 – Theory of Computation 17
Church-Turing Thesis
The equivalence of these models is a mathematical theorem
Church-Turing Thesis: Each of these models captures our intuitive notion of algorithms
The Church-Turing Thesis is not a mathematical statement!
3/2/2020 CS332 – Theory of Computation 18
Multi-Tape TMs
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑎𝑎
Fixed number of tapes 𝑘𝑘 (can’t change during computation) Transitionfunction𝛿𝛿∶𝑄𝑄×Γ𝑘𝑘 →𝑄𝑄×Γ𝑘𝑘 × 𝐿𝐿,𝑅𝑅,𝑆𝑆 𝑘𝑘
Finite control
3/2/2020 CS332 – Theory of Computation 19
Theorem: Every 𝑘𝑘-tape TM 𝑀𝑀 with can be simulated by an equivalent single-tape TM 𝑀𝑀𝑞
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑎𝑎#
Multi-Tape TMs are Equivalent to Single-Tape TMs
Finite control
Finite control
3/2/2020
CS332 – Theory of Computation 20
#
#
Simulating Multiple Tapes
Implementation-Level Description
Oninput𝑤𝑤=𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛 ̇ ̇
1. Formattapeinto#𝑤𝑤̇ 𝑤𝑤 …𝑤𝑤 #⊔#⊔#…# 2. Foreachmoveof𝑀𝑀:1 2 𝑛𝑛
Scan left-to-right, finding current symbols Scan left-to-right, writing new symbols, Scan left-to-right, moving each tape head
If a tape head goes off the right end, insert blank If a tape head goes off left end, move back right
3/2/2020 CS332 – Theory of Computation 21
3/2/2020 CS332 – Theory of Computation 22
Why are Multi-Tape TMs Helpful?
To show a language is Turing-recognizable or decidable, suffices to construct a multi-tape TM
Very helpful for proving closure properties
Ex. Closure of recognizable languages under union. Suppose 𝑀𝑀 is a
1 single-tape TM recognizing 𝐿𝐿1, 𝑀𝑀2 is a single-tape TM recognizing 𝐿𝐿2
3/2/2020 CS332 – Theory of Computation 23
Non-deterministic TMs
At any point in computation, may non-deterministically branch. Accepts iff there exists an accepting branch.
Transitionfunction𝛿𝛿∶𝑄𝑄×Γ →𝑃𝑃(𝑄𝑄×Γ × 𝐿𝐿,𝑅𝑅,𝑆𝑆 ) Ex. NTM for 𝑤𝑤 𝑤𝑤 is a binary number representing the
product of two positive integers 𝑎𝑎, 𝑏𝑏}
3/2/2020 CS332 – Theory of Computation 24
Non-deterministic TMs
Theorem: Every nondeterministic TM has an equivalent deterministic TM
Proof idea: Simulate an NTM 𝑁𝑁 using a 3-tape TM
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Input 𝑤𝑤 to 𝑁𝑁 (read-only) Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3) Address in computation tree
Finite control
𝑤𝑤1 ⊔
𝑤𝑤3 𝑤𝑤4
#
3/2/2020
CS332 – Theory of Computation 25
1
3
3
7
3/2/2020 CS332 – Theory of Computation 26