COSC 340: Theory of Computation

Final Exam Study Guide

Turing Machines, Computability, and Complexity

Sections Covered

  • Section 3.1 (Turing Machines)
  • Section 3.2 (Variants of Turing Machines)
  • Section 3.2 (The Definition of Algorithm)
  • Section 4.1 (Decidable Languages)
  • Section 4.2 (Undecidability)
  • Section 7.1 (Measuring Complexity)
  • Sections 7.2, 7.3, and 7.4 (P / NP / NP-Completeness)

Topics Covered

Section 3.1 (Turing Machines)

  • Know how to read/create Turing machines
    • What language does a Turing machine recognize?
    • Given a language, come up with the Turing machine that recognizes or decides it.
    • Does a Turing machine halt on a string, and if so, does it accept or reject?
    • Does a Turing machine get stuck looping on a string?
  • Know how to represent the configuration of a Turing machine.
  • Know what it means to be Turing recognizable vs. Turing decidable
  • Know what it means to be a recognizer vs. a decider

Section 3.2 (Variants of Turing Machines)

  • Know the three different variants of the standard machine, and whether or not they add any additional power to handle more languages
    • Adding a “stay” option (S)
    • Adding multiple tapes
    • Adding nondeterminism

Section 3.3 (The Definition of Algorithm)

  • Know Hilbert’s problem regarding polynomials and the variations presented in the book

Section 4.1 (Decidable Languages)

  • Know the example languages they mention, and whether or not they are decidable or not (ADFA, ANFA, AREX, EDFA, EQDFA, ACFG, ECFG)
  • Know the power relationship between all of the types of machines we have gone over (DFA/NFA/REGEX < CFG/PDA < TM)
  • Know the power relationship between all of the types of languages we have gone over (regular < deterministic context-free < context-free < Turing decidable < Turing recognizable), and the Venn diagram that shows their relationship

Section 4.2 (Undecidability)

  • Know the difference between countably infinite and uncountably infinite
  • Know some sets that are countable and some that are uncountable
  • Know about the undecidable language ATM
  • Know that there are languages that are not even Turing recognizable

Section 7.1 (Measuring Complexity)

  • Know what running time (time complexity) is, and how to measure it using Big-O notation
  • Know the difference between constant time, linear time, polynomial time, etc.

Sections 7.2, 7.3, and 7.4 (P / NP / NP- Completeness)

  • Know the difference between the classes P, NP, and NP-Complete
  • Know the Venn diagrams on how they relate to each other (there are two possibilities)