CS81: Computability and Logic

Spring 2008

Lecture:

T&Th 2:45-4:00

Professor:

Z Sweedyk

1249 Olin, x78360

z@cs.hmc.edu

Office hours: see schedule

Course mailing list:

cs-81-l@hmc.edu

Grutors:

Richard Bowen rsbowen@gmail.com

Andrew Hunter ahunter@cs.hmc.edu

Will Scott wscott@hmc.edu

What is CS81?

In CS81, we explore the mathematical foundations of computer science. In the first half of the course consider propositional and predicate logic. We'll examine various proof techniques including natural deduction. We conclude this section of the course with Godel's Incompleteness Theorems.

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.

Grades

Grades are based on homework (40%), midterm and final exams (50%), and class participation (10%).

Late Policy

You have five late days that can be used to extend homework assignments across the semester. No other extensions will be allowed unless requested by the dean.

Collaboration

You are highly encouraged to discuss the coursework including homework with other students but you must thoroughly understand and author alone any work you submit for the course.

Course Schedule:

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: CFG and PDA
Thursday 3/27/07	Pumpng Lemma for CFL	Assignment 8	Solution 7
Tuesday 4/1/07	Chomsky Normal Form
Thursday 4/3/07	Properties of CFL	Assignment 9	Solution 8
Tuesday 4/8/07	Parsing
Thursday 4/10/07	Turing machines	Assignment 10	Solution 9
Tuesday 4/15/07	Halting Problem
Thursday 4/17/07	Recursive Sets, Rice's Theorem	Assignment 11	Solution 10
Tuesday 4/22/07	Recursively enumerable sets, Rice's Theorem
Thursday 4/24/07	More reductions	Assignment 12	Solution 11
Tuesday 4/29/07	Church's thesis, Lambda calculus
Thursday 5/1/07	Review		Solution 11