CS 273 (fall 2006)
Topics to be covered on final exam

The final exam will be cumulative, but will concentrate more heavily on material covered since the second midterm. We'll be testing material through the November 16th lecture (Section 5.1 in the book). Material from November 28th (Section 5.2 in the book) is used on Homework 9 and might help your understanding of undecidability, but it won't be directly tested on the final. The material presented on November 30th and December 5th was intended as general background and won't be tested on the final.

The new material for this exam includes:

• Turing machines
  • Formalism: tuple notation, configurations, accepting sequences of configurations.
  • Definition of Turing-recognizable and Turing-decidable, and especially how they differ.
  • Given a Turing machine's state diagram, describe the machine's behavior and language. Be able to produce a sequence of configurations for a specific input string.
  • Design a Turing machine that accepts a specific language, enumerates a specific language, and/or behaves in a specific way. Describe it using a state diagram (very simple problems only!) or pseudo-code.
  • Simulating one type of Turing machine with another: we covered simulating multitape with single tape, normal TM with lazy TM (homework). We might also ask you to cook up a new but similar straightforward simulation, e.g. simulate two-way infinite tape with a normal tape.
  • Dovetailing: simulating a non-deterministic TM with a deterministic one (Theorem 3.16), simulating a finite or infinite number of TM's with a single one (see homework).
  • Theorem 3.21 relating Turing-recognizability and enumeration. Know the relationship and also how the proof works.
  • We're not going to make you produce a long, complex construction in full detail. Rather, concentrate on understanding the key ideas in the above constructions and theorem proofs.
• Simulating a normal computer using a Turing machine.
  • Know how to encode positive integers in binary and how to encode a pair of inputs as one input using a separator character.
  • Know that a Turing machine, automaton, grammar, graph structure, or the like can be encoded as a string, so that you can feed it as input to a Turing machine. Don't worry about the details: it's sufficient to imagine the encoding as an ASCII file containing the normal tuple notation for the machine.
  • Otherwise, this lecture was for your general understanding and won't be tested directly.
• Decidable and undecidable problems
  • Know which standard decision problems for automata (regular lgs and context-free lgs) and Turing machines are decidable, recognizable but not decidable, or undecidable. (See Sections 4.1 and 5.1.)
  • Do the same for the examples we covered during the lectures and homeworks on reductions, especially Turing machine behavior questions (e.g. L₁₁₁).
  • For the decidable or recognizable problems, be able to sketch an algorithm that decides or recognizes it. (The algorithm does not need to be efficient.)
  • Be able to classify new problems as decidable, recognizable but not decidable, or undecidable and provide a brief justification. (Only problems very similar to those we've seen.)
  • In particular, know what closure properties are true and use them to construct a proof of (un)decidability.
  • Know the statement of Rice's theorem.
  • Know that a language is decidable if and only if the language and its complement are both recognizable.
• Proving languages undecidable
  • We know this part of the material is hard. We'll ask questions on it, but we will try to be gentle and we don't expect everyone to be really on top of this stuff.
  • Know how to write a simple diagonalization proof, e.g. show that the reals are uncountable, show that there are more languages than Turing machines (Theorem 4.18).
  • Rough understanding of the diagonalization proof that A_TM is undecidable. We won't make you reproduce this proof on the final. But a brief review might help you e.g. with some short-answer question.
  • Know how to prove that a language is undecidable using a reduction from another language already known to be undecidable. We plan to have a reduction problem on the final, but not a tricky one and we know only some of you will be able to do it.