PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 10:
• Turing Machines
• TM Variants and Closure
Properties
Reading:
Sipser Ch 3.1-3.3
Mark Bun
February 24, 2021
The Basic Turing Machine (TM)
2/24/2021 CS332 – Theory of Computation 2
Tape 𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑎𝑎
Finite
control
…
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts as soon as control reaches
“accept” or “reject” state
Input
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
𝑞𝑞accept
𝑞𝑞reject
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
Example
𝑞𝑞0 𝑞𝑞1
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
• 𝑞𝑞0 ∈ 𝑄𝑄 is the start state
• 𝑞𝑞accept ∈ 𝑄𝑄 is the accept state
• 𝑞𝑞reject ∈ 𝑄𝑄 is the reject state (𝑞𝑞reject ≠ 𝑞𝑞accept)
2/24/2021 CS332 – Theory of Computation 4
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 𝑢𝑢
2/24/2021 CS332 – Theory of Computation 5
1 0 1 0 1 1 1 ⊔
𝑞𝑞5
…
Example: 101𝑞𝑞50111
How a TM Computes
Start configuration: 𝑞𝑞0𝑤𝑤
One step of computation:
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢𝑎𝑎𝑎𝑎 𝑞𝑞𝑞 𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎,𝑅𝑅)
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢 𝑞𝑞𝑞 𝑎𝑎𝑎𝑎𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎, 𝐿𝐿)
• If we are at the left end of the tape in configuration 𝑞𝑞 𝑏𝑏𝑢𝑢,
what configuration do we reach if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎, 𝐿𝐿)?
2/24/2021 CS332 – Theory of Computation 6
How a TM Computes
Start configuration: 𝑞𝑞0𝑤𝑤
One step of computation:
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢𝑎𝑎𝑎𝑎 𝑞𝑞𝑞 𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎,𝑅𝑅)
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢 𝑞𝑞𝑞 𝑎𝑎𝑎𝑎𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎, 𝐿𝐿)
• 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑞𝑞𝑞 𝑎𝑎𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑎𝑎, 𝐿𝐿)
Accepting configuration: 𝑞𝑞 = 𝑞𝑞accept
Rejecting configuration: 𝑞𝑞 = 𝑞𝑞reject
2/24/2021 CS332 – Theory of Computation 7
How a TM Computes
𝑀𝑀 accepts input 𝑤𝑤 if there is a sequence of configurations
𝐶𝐶1, … ,𝐶𝐶𝑘𝑘 such that:
• 𝐶𝐶1 = 𝑞𝑞0𝑤𝑤
• 𝐶𝐶𝑖𝑖 yields 𝐶𝐶𝑖𝑖+1 for every 𝑖𝑖
• 𝐶𝐶𝑘𝑘 is an accepting configuration
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject OR
𝑀𝑀 runs forever on 𝑤𝑤
2/24/2021 CS332 – Theory of Computation 8
Recognizers vs. Deciders
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject OR
𝑀𝑀 runs forever on 𝑤𝑤
𝐴𝐴 is (Turing-)decidable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀
which halts on every input
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject
2/24/2021 CS332 – Theory of Computation 9
Recognizers vs. Deciders
Which of the following is true about the relationship
between decidable and recognizable languages?
a) The decidable languages are a subset of the
recognizable languages
b) The recognizable languages are a subset of the
decidable languages
c) They are incomparable: There might be decidable
languages which are not recognizable and vice versa
2/24/2021 CS332 – Theory of Computation 10
Example: Arithmetic on a TM
The following TM decides MULT = 𝑎𝑎𝑖𝑖𝑏𝑏𝑗𝑗𝑎𝑎𝑘𝑘 𝑖𝑖 × 𝑗𝑗 = 𝑘𝑘}:
On input string 𝑤𝑤:
1. Check 𝑤𝑤 is formatted correctly
2. For each 𝑎𝑎 appearing in 𝑤𝑤:
3. For each 𝑏𝑏 appearing in 𝑤𝑤:
4. Attempt to cross off a 𝑎𝑎. If none exist, reject.
5. If all 𝑎𝑎’s are crossed off, accept. Else, reject.
2/24/2021 CS332 – Theory of Computation 11
Example: Arithmetic on a TM
The following TM decides MULT = 𝑎𝑎𝑖𝑖𝑏𝑏𝑗𝑗𝑎𝑎𝑘𝑘 𝑖𝑖 × 𝑗𝑗 = 𝑘𝑘}:
On input string 𝑤𝑤:
1. Scan the input from left to right to determine whether
it is a member of 𝐿𝐿 𝑎𝑎∗𝑏𝑏∗𝑎𝑎∗
2. Return head to left end of tape
3. Cross off an 𝑎𝑎 if one exists. Scan right until a 𝑏𝑏 occurs.
Shuttle between 𝑏𝑏’s and 𝑎𝑎’s crossing off one of each
until all 𝑏𝑏’s are gone. Reject if all 𝑎𝑎’s are gone but some
𝑏𝑏’s remain.
4. Restore crossed off 𝑏𝑏’s. If any 𝑎𝑎’s remain, repeat step 3.
5. If all 𝑎𝑎’s are crossed off, accept. Else, reject.
2/24/2021 CS332 – Theory of Computation 12
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)
2/24/2021 CS332 – Theory of Computation 13
TM Variants
2/24/2021 CS332 – Theory of Computation 14
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 NFAs have a single accept state
– Adding nondeterminism does not change the languages
recognized by finite automata
– Bonus problem on test: Allowing DFAs to have multiple
passes over their input does not increase their power
Turing machines have an astonishing level of robustness
2/24/2021 CS332 – Theory of Computation 15
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
• Primitive recursive functions
• Cellular automata
…
2/24/2021 CS332 – Theory of Computation 16
Extensions that do not increase the power of
the TM model
• TMs that are allowed to “stay put” instead of moving
left or right
𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑄𝑄 × Γ × 𝐿𝐿,𝑅𝑅, 𝑆𝑆
How would you show that TMs with stay put are no more
powerful than ordinary TMs?
2/24/2021 CS332 – Theory of Computation 17
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 𝑀𝑀’
2/24/2021 CS332 – Theory of Computation 18
Extensions that do not increase the power of
the TM model
• TMs with a 2-way infinite tape, unbounded left to right
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”
2/24/2021 CS332 – Theory of Computation 19
Tape 𝑎𝑎 𝑏𝑏 𝑎𝑎 …
Input
…
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
2/24/2021 CS332 – Theory of Computation 20
Multi-Tape TMs
2/24/2021 CS332 – Theory of Computation 21
𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑎𝑎
Finite
control
𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑎𝑎
Fixed number of tapes 𝑘𝑘 (can’t change during computation)
Transition function 𝛿𝛿 ∶ 𝑄𝑄 × Γ𝑘𝑘 → 𝑄𝑄 × Γ𝑘𝑘 × 𝐿𝐿,𝑅𝑅, 𝑆𝑆 𝑘𝑘
Multi-Tape TMs are Equivalent to Single-Tape TMs
Theorem: Every 𝑘𝑘-tape TM 𝑀𝑀 with can be simulated by an
equivalent single-tape TM 𝑀𝑀𝑞
2/24/2021 CS332 – Theory of Computation 22
𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎
Finite
control
𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑎𝑎 #𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎 #𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎 #
Finite
control
Simulating Multiple Tapes
Implementation-Level Description
On input 𝑤𝑤 = 𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛
1. Format tape into # �̇�𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛# ⊔̇ # ⊔̇ # … #
2. For each move of 𝑀𝑀:
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
2/24/2021 CS332 – Theory of Computation 23
Why are Multi-Tape TMs Helpful?
To show a language is Turing-recognizable or decidable, it’s
enough to construct a multi-tape TM
Often easier to construct multi-tape TMs
Ex. Decider for 𝑎𝑎𝑖𝑖𝑏𝑏𝑗𝑗 𝑖𝑖 > 𝑗𝑗}
2/24/2021 CS332 – Theory of Computation 24
Why are Multi-Tape TMs Helpful?
To show a language is Turing-recognizable or decidable, it’s
enough to construct a multi-tape TM
Very helpful for proving closure properties
Ex. Closure of recognizable languages under union. Suppose 𝑀𝑀1 is a
single-tape TM recognizing 𝐿𝐿1, 𝑀𝑀2 is a single-tape TM recognizing 𝐿𝐿2
2/24/2021 CS332 – Theory of Computation 25
Why are Multi-Tape TMs Helpful?
To show a language is Turing-recognizable or decidable, it’s
enough to construct a multi-tape TM
Very helpful for proving closure properties
Ex. Closure of recognizable languages under union. Suppose 𝑀𝑀1 is a
single-tape TM recognizing 𝐿𝐿1, 𝑀𝑀2 is a single-tape TM recognizing 𝐿𝐿2
2/24/2021 CS332 – Theory of Computation 26
Closure Properties
The Turing-decidable languages are closed under:
The Turing-recognizable languages are closed under:
2/24/2021 CS332 – Theory of Computation 27
• Union
• Concatenation
• Star
• Intersection
• Reverse
• Complement
• Union
• Concatenation
• Star
• Intersection
• Reverse
BU CS 332 – Theory of Computation
The Basic Turing Machine (TM)
Slide Number 3
Formal Definition of a TM
Configuration of a TM: Formally
How a TM Computes
How a TM Computes
How a TM Computes
Recognizers vs. Deciders
Recognizers vs. Deciders
Example: Arithmetic on a TM
Example: Arithmetic on a TM
Back to Hilbert’s Tenth Problem
TM Variants
How Robust is the TM Model?
TMs are equivalent to…
Extensions that do not increase the power of the TM model
Extensions that do not increase the power of the TM model
Extensions that do not increase the power of the TM model
Formalizing the Simulation
Multi-Tape TMs
Multi-Tape TMs are Equivalent to Single-Tape TMs
Simulating Multiple Tapes
Why are Multi-Tape TMs Helpful?
Why are Multi-Tape TMs Helpful?
Why are Multi-Tape TMs Helpful?
Closure Properties