The final exam will be Thursday, December 13 at 7:30pm in Austin 307.
This is a course on the theory of computing. See the syllabus for details.
TTh 10:45-12:15 and 5:30-6:30pm or by appointment.
If you have obtained a password then you can check your grades as I have them recorded. This will be the only way that you can learn your grade at the end of the term before it has been posted on the student desktop.
You can obtain a password from me. To obtain one by email, send me email giving your name, the course, and the password that you want. Choose a string of 4 or 5 letters/digits. Be careful about upper and lower case letters. Your password will be exactly what you send to me.
[8/16/01] We covered notation and terminology from chapter 0 of the text. We began looking at proof methods, including forward proof, backward proof and proof by contradiction.
[8/21/01] We did examples of proofs. You should read the examples in chapter 0 of the text.
[8/23/01] We began studying finite state computation. We went through both the intuition and the definition of finite state machines (also called deterministic finite automata, or DFAs). This material is in chapter 1 of the text.
[8/28/01] We continued looking at finite state machines and introduced regular expressions.
[8/30/01] We looked more at regular expressions and nondeterministic finite state machines. They are a kind of model that is intermediate between regular expressions and deterministic finite state machines.
[9/4/01] Nondeterministic finite automata with epsilon-transitions were introduced, and we saw how to eliminate the epsilon-transitions. We saw how to convert an arbitrary DFA into an equivalent regular expression by going through generalized finite automata.
[9/6/01] Quiz 1. We finished the conversion theorems by showing how to convert a regular expression to an NFA with epsilon transitions. We defined the class of regular languages. Then we began to look at how to prove that a language is not regular.
[9/11/01] We did examples of proving that languages are not regular. Then we briefly turned to closure results for regular languages.
[9/13/01] We did went over the homework and looked more at closure results. Then the general area of context-free languages and push-down machines was introduced.
[9/18/01] We defined context-free grammars and context-free languages. This material is in chapter 2 of the text.
[9/20/01] Quiz 2. We discussed more material on context-free grammars and push-down machines.
[9/25/01] We went through examples of context-free grammars and derivations.
[9/27/01] We went over Turing machines, relationships between models of computation and the Church/Turing thesis.
[10/2/01] We defined computablility and explored some computable problems about finite state machines.
[10/4/01] We proved that the halting problem is undecidable. The proof is a diagonalization over all purported solutions, showing that none of them can possibly work.
[10/9/01] We looked at more undeciable problems.
[10/11/01] We proved Rice's theorem.
[10/18/01] Quiz 3. We defined Turing recognizable problems.
[10/23/01] We introduced reductions and the concept of completeness.
[10/25/01] We proved that Post's correspondence problem is undecidable.
[10/30/01] We showed that Post's correspondence problem is m-complete. We looked at Hilbert's tenth problem.
[11/1/01] We went through a proof that the ambiguity problem for context-free grammars is undecidable, and discussed recursively enumerable sets.
[11/5/01] We will begin looking at complexity theory.
[11/7/01] Quiz 4.