CS代考计算机代写 c++ BU CS 332 – Theory of Computation

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
4/1/2020 CS332 ‐ Theory of Computation 2

4/1/2020 CS332 ‐ Theory of Computation 3

4/1/2020 CS332 ‐ Theory of Computation 4

Midterm II Topics
4/1/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
4/1/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.
4/1/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 􏶀􏵾􏶁)
4/1/2020
CS332 ‐ Theory of Computation 8

Undecidability (4.2)
• Know the definitions of countable and uncountable sets and how to prove countability and uncountability
• Understand how diagonalization is used to prove the existence of explicit undecidable languages ( 􏶂􏶃 in the book, or 􏶂􏶃 from lecture)
• Know that a language is decidable iff it is recognizable and co‐recognizable, and understand the proof
4/1/2020 CS332 ‐ Theory of Computation 9

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 computation history method. However, you should know that the language 􏶀􏵾􏶁 is undecidable, and reducing from it might be useful.
4/1/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
4/1/2020 CS332 ‐ Theory of Computation 11

Tips for Preparing Exam Solutions
4/1/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
4/1/2020 CS332 ‐ Theory of Computation 13

Simulation arguments, constructing deciders
• Fullcreditforaclearandcorrectdescriptionofthenewmachine • Stillagoodideatoprovideanexplanation
(partial credit, clarifying ambiguity)
4/1/2020 CS332 ‐ Theory of Computation 14

Undecidability proofs
4/1/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
4/1/2020 CS332 ‐ Theory of Computation 16

Practice Problems
4/1/2020 CS332 ‐ Theory of Computation 17

4/1/2020 CS332 ‐ Theory of Computation 18

4/1/2020 CS332 ‐ Theory of Computation 19

4/1/2020 CS332 ‐ Theory of Computation 20

4/1/2020 CS332 ‐ Theory of Computation 21

4/1/2020 CS332 ‐ Theory of Computation 22

Decidability and Recognizability
4/1/2020 CS332 ‐ Theory of Computation 23

Let
Show that is decidable
􏶄
4/1/2020 CS332 ‐ Theory of Computation
24

Prove that is recognizable
4/1/2020 CS332 ‐ Theory of Computation 25

Prove that if and are decidable, then so is
4/1/2020 CS332 ‐ Theory of Computation 26

Countable and Uncountable Sets
4/1/2020 CS332 ‐ Theory of Computation 27

Show that the set of all valid (i.e., compile without errors) C++ programs is countable
4/1/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.
4/1/2020 CS332 ‐ Theory of Computation 29

Undecidability and Unrecognizability
4/1/2020 CS332 ‐ Theory of Computation 30

Prove or disprove: If and are recognizable, then so is
4/1/2020 CS332 ‐ Theory of Computation
31

Prove that the language
􏶅􏶆 ∗
4/1/2020 CS332 ‐ Theory of Computation
32
is undecidable

Give a nonregular language such that
or prove that none exists
4/1/2020 CS332 ‐ Theory of Computation 33

Give an undecidable language such that
or prove that none exists
4/1/2020 CS332 ‐ Theory of Computation 34

Give an undecidable language such that
or prove that none exists
4/1/2020 CS332 ‐ Theory of Computation 35