PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 11:
• TM Variants and Closure
Properties
• Church-Turing Thesis
Reading:
Sipser Ch 3.2
Mark Bun
March 1, 2021
TM Variants
2/28/2021 CS332 – Theory of Computation 2
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/28/2021 CS332 – Theory of Computation 3
Multi-Tape TMs
2/28/2021 CS332 – Theory of Computation 4
𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑎𝑎
Finite
control
𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑐𝑐
Fixed number of tapes 𝑘𝑘 (can’t change during computation)
Transition function 𝛿𝛿 ∶ 𝑄𝑄 × Γ𝑘𝑘 → 𝑄𝑄 × Γ𝑘𝑘 × 𝐿𝐿,𝑅𝑅, 𝑆𝑆 𝑘𝑘
How to Simulate It
To show that a TM variant is no more powerful than the
basic, single-tape TM:
Show that if 𝑀𝑀 is any variant machine, there exists a basic,
single-tape TM 𝑀𝑀𝑀 that can simulate 𝑀𝑀
(Usual) parts of the simulation:
• Describe how to initialize the tapes of 𝑀𝑀𝑀 based on the
input to 𝑀𝑀
• Describe how to simulate one step of 𝑀𝑀’s computation
using (possibly many steps of) 𝑀𝑀𝑀
3/1/2021 CS332 – Theory of Computation 5
Multi-Tape TMs are Equivalent to Single-Tape TMs
Theorem: Every 𝑘𝑘-tape TM 𝑀𝑀 with can be simulated by an
equivalent single-tape TM 𝑀𝑀𝑀
2/28/2021 CS332 – Theory of Computation 6
𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎
Finite
control
𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎
⊔ 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑐𝑐 #𝑎𝑎 𝑏𝑏 ⊔ 𝑎𝑎 #𝑏𝑏 𝑏𝑏 𝑎𝑎 𝑎𝑎 #
Finite
control
Simulating Multiple Tapes
Implementation-Level Description of 𝑀𝑀𝑀
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/28/2021 CS332 – Theory of Computation 7
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/28/2021 CS332 – Theory of Computation 8
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
3/1/2021 CS332 – Theory of Computation 9
What’s wrong with this
construction?
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/28/2021 CS332 – Theory of Computation 10
Closure Properties
The Turing-decidable languages are closed under:
The Turing-recognizable languages are closed under:
2/28/2021 CS332 – Theory of Computation 11
• Union
• Concatenation
• Star
• Intersection
• Reverse
• Complement
• Union
• Concatenation
• Star
• Intersection
• Reverse
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
Transition function 𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑃𝑃(𝑄𝑄 × Γ × 𝐿𝐿,𝑅𝑅, 𝑆𝑆 )
2/28/2021 CS332 – Theory of Computation 12
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
3/1/2021 CS332 – Theory of Computation 13
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
3/1/2021 CS332 – Theory of Computation 14
What is the language of this
NTM?
Nondeterministic TMs
Ex. Given TMs 𝑀𝑀1 and 𝑀𝑀2, construct an NTM recognizing
𝐿𝐿 𝑀𝑀1 ∪ 𝐿𝐿 𝑀𝑀2
3/1/2021 CS332 – Theory of Computation 15
Nondeterministic TMs
Ex. NTM for 𝑤𝑤 𝑤𝑤 is a binary number representing the
product of two positive integers 𝑎𝑎, 𝑏𝑏}
3/1/2021 CS332 – Theory of Computation 16
Nondeterministic TMs
An NTM 𝑁𝑁 accepts input 𝑤𝑤 if when run on 𝑤𝑤 it accepts on
at least one computational branch
𝐿𝐿 𝑁𝑁 = {𝑤𝑤 ∣ 𝑁𝑁 accepts input 𝑤𝑤}
An NTM 𝑁𝑁 is a decider if on every input, it halts on every
computational branch
3/1/2021 CS332 – Theory of Computation 17
Nondeterministic TMs
Theorem: Every nondeterministic TM can be simulated by
an equivalent deterministic TM
Proof idea:
Systematically try all 1-step computations, all 2-step
computations, … and see if one of them accepts
2/28/2021 CS332 – Theory of Computation 18
Nondeterministic TMs
Theorem: Every nondeterministic TM has an equivalent
deterministic TM
Proof idea: Simulate an NTM 𝑁𝑁 using a 3-tape TM
2/28/2021 CS332 – Theory of Computation 19
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Finite
control
𝑤𝑤1 ⊔ # 𝑤𝑤3 𝑤𝑤4
1 3 3 7
Input 𝑤𝑤 to 𝑁𝑁 (read-only)
Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3)
Address in computation tree
2/28/2021 CS332 – Theory of Computation 20
Enumerators
• Starts with two blank tapes
• Prints strings to printer
𝐿𝐿(𝐸𝐸) = {strings eventually printed by 𝐸𝐸}
• May never terminate (even if language is finite)
• May print the same string many times
3/1/2021 CS332 – Theory of Computation 21
Finite
control
Work tape
“Printer”
Enumerator Example
3/1/2021 CS332 – Theory of Computation 22
What is the language enumerated by the following program?
“Write 1 to the work tape. Repeat the following forever:
Multiply the binary number on the work tape by 2, and copy
the result to the printer.”
a) 𝑥𝑥 𝑥𝑥 is a binary number 𝑛𝑛2 for some 𝑛𝑛 ≥ 1}
b) {𝑥𝑥 | 𝑥𝑥 is a binary number 2𝑛𝑛 for some 𝑛𝑛 ≥ 0}
c) {𝑥𝑥 | 𝑥𝑥 is a binary number 22
𝑛𝑛
for some 𝑛𝑛 ≥ 0}
d) None of the above
Enumerable = Turing-Recognizable
Theorem: A language is Turing-recognizable ⇔ some
enumerator enumerates it
⇐ Start with an enumerator 𝐸𝐸 for 𝐴𝐴 and give a TM
3/1/2021 CS332 – Theory of Computation 23
Enumerable = Turing-Recognizable
Theorem: A language is Turing-recognizable ⇔ some
enumerator enumerates it
⇒ Start with a TM 𝑀𝑀 for 𝐴𝐴 and give an enumerator
3/1/2021 CS332 – Theory of Computation 24
Enumerable = Turing-Recognizable
Theorem: A language is Turing-recognizable ⇔ some
enumerator enumerates it
⇒ Start with a TM 𝑀𝑀 for 𝐴𝐴 and give an enumerator
3/1/2021 CS332 – Theory of Computation 25
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/28/2021 CS332 – Theory of Computation 26
Church-Turing Thesis
The equivalence of these models is a mathematical
theorem
Church-Turing Thesis v1: The basic TM (hence all of these
models) captures our intuitive notion of algorithms
Church-Turing Thesis v2: Any physically realizable model
of computation can be simulated by the basic TM
The Church-Turing Thesis is not a mathematical
statement!
3/1/2021 CS332 – Theory of Computation 27
BU CS 332 – Theory of Computation
TM Variants
TMs are equivalent to…
Multi-Tape TMs
How to Simulate It
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
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Slide Number 20
Enumerators
Enumerator Example
Enumerable = Turing-Recognizable
Enumerable = Turing-Recognizable
Enumerable = Turing-Recognizable
TMs are equivalent to…
Church-Turing Thesis