Microsoft PowerPoint – CS332-Lec11-ann
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
3/3/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
…
3/3/2021 CS332 ‐ Theory of Computation 3
Multi‐Tape TMs
3/3/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/3/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
3/3/2021 CS332 ‐ Theory of Computation 6
𝑏 𝑏 𝑎 𝑎
Finite
control
𝑎 𝑏 ⊔ 𝑎
⊔ 𝑏 𝑎 𝑎
⊔ 𝑏 𝑎 𝑎 𝑐 #𝑎 𝑏 ⊔ 𝑎 #𝑏 𝑏 𝑎 𝑎 #
Finite
control
Simulating Multiple Tapes
Implementation‐Level Description of
On input
1. Format tape into
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
3/3/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 𝑎 𝑏 𝑖 𝑗
3/3/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 𝑀 is a
single‐tape TM recognizing 𝐿 , 𝑀 is a single‐tape TM recognizing 𝐿
3/3/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 𝑀 is a
single‐tape TM recognizing 𝐿 , 𝑀 is a single‐tape TM recognizing 𝐿
3/3/2021 CS332 ‐ Theory of Computation 10
Closure Properties
The Turing‐decidable languages are closed under:
The Turing‐recognizable languages are closed under:
3/3/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
3/3/2021 CS332 ‐ Theory of Computation 12
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
3/3/2021 CS332 ‐ Theory of Computation 13
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
3/3/2021 CS332 ‐ Theory of Computation 14
What is the language of this
NTM?
Nondeterministic TMs
Ex. Given TMs and , construct an NTM recognizing
3/3/2021 CS332 ‐ Theory of Computation 15
Nondeterministic TMs
Ex. NTM for is a binary number representing the
product of two positive integers
3/3/2021 CS332 ‐ Theory of Computation 16
Nondeterministic TMs
An NTM accepts input if when run on it accepts on
at least one computational branch
An NTM is a decider if on every input, it halts on every
computational branch
3/3/2021 CS332 ‐ Theory of Computation 17