- 2016 Dec 13 04:26:51 PM: Changed date to Fall 2015 - No changes to material
- 2015 Dec 15 02:32:34 PM: Updated for Fall 2015

**Material**- Topics from Exams 1 and 2
- Material from chapters 17, 18, 19, 20, 21, and 28, as specified
- Points distribution: about 200 points total with roughly 55 points on Language and Regular Language topics, about 45 points on Context Free Language topics, and about 90 points for Turing Machines, Halting and Decidability (65 points), and NP Completeness (25 points).
**Chapter 17 - Turing Machines**- Give the formal definition of a TM.
- Describe the contents of a TM configuration, written as a 4-tuple.

- Describe what it means for a TM to
**decide**a language and to be a decider, and for a language to be**decidable**. - Describe what it means for a TM to
**semidecide**a language and to be a semidecider, and for a language to be**semidecidable**.

- Draw or interpret a TM that implements a specified algorithm, with or without the macro language.

- Describe the relationship among single tape deterministic TM, multi-tape deterministic TM, and nondeterministic TM.

- Describe how to lexicographically enumerate all TMs.
- Describe the input and operation of U, the Universal Turing Machine (aka UTM).

**Chapter 18 - The Church-Turing Thesis**- Give a simple counting proof that there are more languages than there are Turing Machines.
- Describe the Church-Turing Thesis and its relevance.

**Chapter 19 - Unsolvability of the Halting Problem**- Define the language
**H**. - Show that the language
**H**is semidecidable.

- Define the TM
*Trouble*as defined in the text. - Use the TM
*Trouble*to prove that**H**is not decidable.

- Define the language
**Chapter 20 - Decidability and Semidecidable Languages**- Define the language classes D and SD
- Explain why D is a subset of SD (ie why every language in D is also in SD)
- Give a counting argument that not all languages are in SD.

- Show that the class D is closed under complement.
- Show that if
*L*and ¬*L*are in the class SD, then L is in D. - Show that the class SD is NOT closed under complement.

- Reproduce and be able to use the diagram on page 445 of your text (excluding parts we didn't discuss).

**Chapter 21 - Decidability and Semidecidable Proofs**- Describe and give examples of the general concept of reducing one problem to another.
- Describe the relative difficulties of problems in a given reduction.
- Given a reduction from languages L1 to L2, describe what can be proved
regarding whether or not L1 and L2 are or are not in D.

- Construct a proof that uses reduction to show that a language such as
H
_{ε}is not in D. - Describe how proving a language is not in D makes it easier to subsequently prove that other languages are not in D.

**Chapter 28 - Time Complexity Classes (ie P, NP, NP-Hard, NP-Complete)**~~Explain how to express an instance of a problem as a language.~~

- Define the class
**P**. - Explain how to show that a language is in
*P*.

- Define the class
**NP**(two definitions)

- Explain how the concept of
**reduction**applies to problems in NP. - State the Cook-Levin Theorem and explain it's significance.

- Define the term
**NP-Hard**. - Define the term
**NP-Complete**. - Explain what you can say about the hardness of solving
**NP-Complete**languages as compared to solving other languages in NP. - Explain the significance of
**NP-Complete**languages. - Explain the significance of finding a polynomial time solution to an NP-Complete language.
- Explain how one NP-Complete language can be used to show that another language is NP-complete
- Show that P = NP!