CS 373: Introduction to Theory of Computation
Spring 2013
The final exam will be cumulative, but will concentrate on the
material covered since the second midterm (lecture 19 through 27;
chapters 3, 4, and 5 of Sipser's book). Key skills that will be
tested in the final include the skill sets for midterm 1 and
midterm 2, and in addition the following new material:
- Formal Definitions of Turing Machines
- Know the formal definition of: Turing machines; instantaneous
description; single step and a sequence of steps; acceptance
of string; language recognized by a Turing machine; Turing
recognizable languages or recursively enumerable languages;
Turing decidable languages; Turing enumerators.
- For an example Turing machine, know how to: describe it precisely
using a transition diagram, or formal tuple notation; compute
the behavior on a specific input; describe the language recognized
by a Turing machine.
- Know how to describe a new variant of Turing machine/automata
formally, given its informal description in words.
- Turing Machine Constructions
- Design a formal Turing machine for a given language.
- Understand the simulations of different computational models on
the Turing machine presented in class and the book. Concentrate
on understanding the key ideas in these constructions and theorem
proofs, rather than the detailed construction.
- Constructing (informal) Turing simulation of new models of
computation or for variants of the Turing machine model.
- Decidability and Recursive Enumerability
- Know what it means for a language to be: decidable; undecidable;
Turing recognizable/recursively enumerable; not recursively
enumerable/Turing recognizable.
- Know the relationship between recognition and enumerablity. That is,
a language is Turing recognizable iff it is recursively enumerable;
a language is decidable iff it can be enumerated in a canonical
order (problem 3.18 and done in discussion 9).
- Know the relationship between decidability and recursive
enumerability: decidability implies recursive enumerability; a
language is decidable iff both the language and its complement
are recursively enumerable.
- Know how to show that a language is decidable or recursively
enumerable, by giving a pseudo-code of an algorithm.
- Ability to classify languages as regular/decidable/recursively
enumerable/not recursively enumerable.
- Know the definitions of standard languages like the diagonal
language, the universal language (ATM), halting problem, etc.
Know which ones are undecidable/recursively enumerable/not
recursively enumerable.
- Proof Techniques
- Understand the diagonalization proof showing that the diagonal
language is not recursively enumerable.
- Understand diagonalization as a proof technique, for example, as
how it implies that any model for decidable languages will be
incomplete.
- Understand the definition of reductions.
- Understand how reductions can be used to both prove
positive results (decidability/recursive enumerability) and
negative results (undecidability/recursive enumerability).
- Know how to prove that one language reduces to another by describing
a reduction and proving that it satisfies the properties of a
reduction.
- Know how to use reductions to show a specific language to be
undecidable/non-recursive-enumerable.
- Understand the statement of Rice's Theorem.
- Understand the proof of Rice's Theorem to get a better understanding
of how to construct and use reductions --- we will not ask you to
reproduce it.
- Understand how to use Rice's Theorem to draw conclusions about a
given language.
- Closure Properties
- Know under which operations decidable and recursively enumerable
languages are closed.
- Know how to use closure properties to draw conclusions about other
operations and languages.