Harvey Mudd College
Spring 2010
Computer Science 81

Computability and Logic

What this course is about

 

First we’ll look at logic, both propositional and predicate forms, with an emphasis on the distinction between validity (truth) and provability (derivation). We’ll gain some experience in doing proofs in a style known as “natural deduction”, both for propositional and predicate logic. This will be helpful as a way of outlining proofs for the rest of your careers. We will also look at several more mechanical methods of assessing the validity of a formula. We’ll also examine the relationships between logical formulas and program correctness.

 

We will next review finite-state automata and their relationship to languages and regular expressions. We’ll look at the

applications and limitations of these machines, then move on to the more powerful pushdown automata. We will show how pushdown automata exactly characterize the larger family of languages known as context-free languages. These are the languages generated by grammars of the type you studied in CS 60. We’ll look at the applications of these automata, and also show their limitations.

 

Next we’ll look at Turing machines, which are even more computationally powerful. We’ll discover what kind of grammars are equivalent to Turing machines as well as some specialized Turing machine models. We will also discuss the lambda calculus, an alternate basis for computability and the basis for modern functional programming languages, as well as the partial recursive function formulation.

 

As with other families of machines, Turing machines have their imitations. We will show how to prove that certain problems cannot be solved algorithmically, even ones not apparently related to Turing machines. 

 

We will close by examining the connections between logic and computability in more depth, and with Gödel’s famous Incompleteness Theorem.

Instructor

Bob Keller, 1253 Olin (office hours 2:30-4:00 MW, or whenever I'm in), keller @ cs·hmc·edu, x 18483, AIM: MuddProf
 

Grutors (Consulting Hours in Platt Living Room)

Greg Bickerman: Sunday 9-11 pm

Sonja Bohr: Monday 9-11 pm

Bob Chen: Sunday 7-9 pm

Karen Gragg: Saturday 3-5 pm

Yaniv Ovadia: Monday 7-9 pm

 

Catalog Description

An introduction to some of the mathematical foundations of computer science, particularly logic, automata, and

computability theory. Develops skill in constructing and writing proofs, and demonstrates the applications of the aforementioned areas to problems of practical significance. Prerequisites: Math 55, Computer Science 60. 3 credit hours. (Both semesters.)

 

Requirements and Grading

 

Textbooks

 

 

Lecture Slides and Assignments (will be posted as each is given) This outline may undergo some revision.