During the second half of the course we explore computability theory. We examine a variety of computatonal models in depth, including finite automata, pushdown autamata, and Turing machines. We study the methods for proving a problem solvable or unsolvable under each model. We conclude with a review of other computational models including lambda calculus.
Date | Topic | Assigment | Links |
Tuesday 1/22/07 |
Elementary notions and notation | ||
Thursday 1/24/07 |
Propositional calculus Refutation trees |
Assignment 1 | |
Tuesday 1/29/07 |
Natural deduction | ||
Thursday 1/31/07 |
Intro to predicate logic | Assignment 2 | Solution 1 |
Tuesday 2/5/07 |
Equivalences Formal proofs in predicate logic |
||
Thursday 2/7/07 |
Formal proofs cont. | Assignment 3 | Solution 2 |
Tuesday 2/12/07 |
Refutation trees revisited | ||
Thursday 2/14/07 |
Reasoning with equality | Assignment 4 | Solution 3 |
Tuesday 2/19/07 |
Computational logic | ||
Thursday 2/21/07 |
Computation logic cont. Soundness and completeness |
Assignment 5 | Solution 4 |
Tuesday 2/26/07 |
Review of logic | ||
Thursday 2/28/07 |
Regular expressions and finite automata | Solution 5 | |
Tuesday 3/4/07 |
Midterm Exam | ||
Thursday 3/6/07 |
Regular language | Assignment 6 | |
Tuesday 3/11/07 |
Myhill-Nerode Theorem | ||
Thursday 3/13/07 |
Pumping Lemma | Assignment 7 | Solution 6 |
Tuesday 3/18/07 |
Spring Break | ||
Thursday 3/20/07 |
Spring Break | ||
Tuesday 3/25/07 |
Context-free languages | ||
Thursday 3/27/07 |
Context-free languages cont. | Assignment 8 | Solution 7 |
Tuesday 4/1/07 |
Push down automata, pumping lemma | ||
Thursday 4/3/07 |
Chomsky Normal Form, proof of pumping lemma | Assignment 9 | Solution 8 |
Tuesday 4/8/07 |
Parsing | ||
Thursday 4/10/07 |
Parsing cont. | Assignment 10 | Solution 9 |
Tuesday 4/15/07 |
Turing machines | ||
Thursday 4/17/07 |
Computability, Halting problem | Assignment 11 | Solution 10 |
Tuesday 4/22/07 |
Reductions, Rice's Theorem(1) | ||
Thursday 4/24/07 |
Recursive enumerable sets, Rice's Theorem(2) | Assignment 12 | Solution 11 |
Tuesday 4/29/07 |
Church's thesis, Lambda calculus | ||
Thursday 5/1/07 |
Review | Solution 11 |