BU CS 332 – Theory of Computation
Lecture 17:
• Midterm II review
Reading:
Sipser Ch 3.1-5.1, 5.3
Mark Bun March 30, 2020
Format of the Exam
3/30/2020 CS332 – Theory of Computation 2
3/30/2020 CS332 – Theory of Computation 3
3/30/2020 CS332 – Theory of Computation 4
Midterm II Topics
3/30/2020 CS332 – Theory of Computation 5
Turing Machines (3.1, 3.3)
• Know the three different “levels of abstraction” for defining Turing machines and how to convert between them: Formal/state diagram, implementation-level, and high-level
• Know the definition of a configuration of a TM and the formal definition of how a TM computes
• Know how to “program” Turing machines by giving implementation-level descriptions
• Understand the Church-Turing Thesis
3/30/2020 CS332 – Theory of Computation 6
TM Variants (3.2)
• Understand the following TM variants: Multi-tape TMs, Nondeterministic TMs, Enumerators
• Know how to give a simulation argument (implementation-level description) to compare the power of TM variants
• Understand the specific simulation arguments we’ve seen: multi-tape TM by basic TM, nondeterministic TM by basic TM, enumerator by basic TM and basic TM by enumerator.
3/30/2020 CS332 – Theory of Computation 7
Decidability (4.1)
• Understand how to use a TM to simulate another machine (DFA, another TM)
• Know the specific decidable languages from language theory that we’ve discussed, and how to decide them: 𝐴𝐴 ,𝐸𝐸 ,𝐸𝐸𝐸𝐸 ,𝐴𝐴 ,𝐸𝐸 ,etc.
• Know how to use a reduction to one of these languages to show that a new language is decidable
𝐷𝐷𝐷𝐷𝐷𝐷 𝐷𝐷𝐷𝐷𝐷𝐷 𝐷𝐷𝐷𝐷𝐷𝐷
𝐶𝐶𝐷𝐷𝐶𝐶 𝐶𝐶𝐷𝐷𝐶𝐶
• (You don’t need to know details of what Chomsky Normal Form is, but understand how it is used to prove
decidability of 𝐴𝐴 3/30/2020
𝐶𝐶𝐷𝐷𝐶𝐶
)
CS332 – Theory of Computation 8
Undecidability (4.2)
• Know the definitions of countable and uncountable sets and how to prove countability and uncountability
existence of explicit undecidable languages (𝐴𝐴 book, or 𝑆𝑆𝐴𝐴𝑇𝑇𝑇𝑇 from lecture)
• Understand how diagonalization is used to prove the
• Know that a language is decidable iff it is recognizable and co-recognizable, and understand the proof
3/30/2020 CS332 – Theory of Computation 9
𝑇𝑇𝑇𝑇
in the
Reducibility (5.1)
• Understand how to use a reduction (contradiction argument) to prove that a language is undecidable
• Know the reductions showing that 𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 , 𝑇𝑇𝑇𝑇
𝐸𝐸𝑇𝑇𝑇𝑇, 𝑅𝑅𝐸𝐸𝑅𝑅𝑅𝑅𝐻𝐻𝐴𝐴𝑅𝑅𝑇𝑇𝑇𝑇, 𝐶𝐶𝐶𝐶𝐻𝐻𝑇𝑇𝑇𝑇, 𝐸𝐸𝐸𝐸𝑇𝑇𝑇𝑇 are undecidable
• You are not responsible for understanding the
know that the language 𝐴𝐴𝐻𝐻𝐻𝐻 is undecidable, and 𝐶𝐶𝐷𝐷𝐶𝐶
computation history method. However, you should
reducing from it might be useful.
3/30/2020 CS332 – Theory of Computation 10
Mapping Reducibility (5.3)
• Understand the definition of a computable function
• Understand the definition of a mapping reduction
• Know how to use mapping reductions to prove decidability, undecidability, recognizability, and unrecognizability
3/30/2020 CS332 – Theory of Computation 11
Tips for Preparing Exam Solutions
3/30/2020 CS332 – Theory of Computation 12
True or False
• It’s all about the justification!
• The logic of the argument has to be clear
• Restating the question is not justification; we’re
looking for some additional insight
3/30/2020 CS332 – Theory of Computation 13
Simulation arguments, constructing deciders
• Full credit for a clear and correct description of the new machine • Still a good idea to provide an explanation
(partial credit, clarifying ambiguity)
3/30/2020 CS332 – Theory of Computation 14
Undecidability proofs
3/30/2020 CS332 – Theory of Computation 15
Uncountability proofs
• The 2-D table is useful for thinking about diagonalization, but is not essential to the argument
• The essential part of the proof is the construction of the “inverted diagonal” element, and the proof that it works
3/30/2020 CS332 – Theory of Computation 16
Practice Problems
3/30/2020 CS332 – Theory of Computation 17
3/30/2020 CS332 – Theory of Computation 18
3/30/2020 CS332 – Theory of Computation 19
3/30/2020 CS332 – Theory of Computation 20
3/30/2020 CS332 – Theory of Computation 21
3/30/2020 CS332 – Theory of Computation 22
Decidability and Recognizability
3/30/2020 CS332 – Theory of Computation 23
Let 𝐴𝐴={𝐷𝐷|
𝐷𝐷 is a DFA that does not accept any string
containing an odd number of 1′s} Show that 𝐴𝐴 is decidable
3/30/2020 CS332 – Theory of Computation 24
Prove that 𝐸𝐸TM is recognizable
3/30/2020 CS332 – Theory of Computation 25
Prove that if 𝐴𝐴 and 𝐵𝐵 are decidable, then so is 𝐴𝐴\𝐵𝐵
3/30/2020 CS332 – Theory of Computation 26
Countable and Uncountable Sets
3/30/2020 CS332 – Theory of Computation 27
Show that the set of all valid (i.e., compile without errors) C++ programs is countable
3/30/2020 CS332 – Theory of Computation 28
A Celebrity Twitter Feed is an infinite sequence of ASCII strings, each with at most 140 characters. Show that the set of Celebrity Twitter Feeds is uncountable.
3/30/2020 CS332 – Theory of Computation 29
Undecidability and Unrecognizability
3/30/2020 CS332 – Theory of Computation 30
Prove or disprove: If 𝐴𝐴 and 𝐵𝐵 are recognizable, then so is 𝐴𝐴 \ 𝐵𝐵
3/30/2020 CS332 – Theory of Computation 31
Prove that the language 𝐴𝐴𝐻𝐻𝐻𝐻TM =
{ 𝑀𝑀 |𝑀𝑀 is a TM and 𝐻𝐻 𝑀𝑀 = Σ∗} is undecidable
3/30/2020 CS332 – Theory of Computation 32
Give a nonregular language 𝐴𝐴 such that 𝐴𝐴 ≤𝑚𝑚 𝐻𝐻(0∗1∗) or prove that none exists
3/30/2020 CS332 – Theory of Computation 33
Give an undecidable language 𝐴𝐴 such that 𝐴𝐴 ≤𝑚𝑚 𝐻𝐻(0∗1∗) or prove that none exists
3/30/2020 CS332 – Theory of Computation 34
Give an undecidable language 𝐴𝐴 such that 𝐻𝐻(0∗1∗) ≤𝑚𝑚 𝐴𝐴 or prove that none exists
3/30/2020 CS332 – Theory of Computation 35