Harvey Mudd College
Spring 2009
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 proofs. 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 conclude with a look at Godel’s famous Incompleteness Theorem.

Instructor

Bob Keller, 1253 Olin (office hours 4:15-5:30 MTW, or whenever I'm in), keller A T cs.hmc.edu, x 18483, AIM: MuddProf
 

Grutors

Denis Aleshin
Richard Bowen

Josh Ehrlich

Kaylin Spitz


Grutor Consulting Hours


Sat, 1-3 pm, Platt Campus Center Living Room (ground floor), Josh Ehrlich, joshua_ehrlich A T hmc.edu

Sat. 3-5 pm, Platt Campus Center Living Room, Kaylin Spitz, Kaylin_M_Spitz A T hmc.edu

Sun. 6-8 pm, Beckman Hall, CS Terminal Room (underground),  Denis Aleshin, daleshin A T hmc.edu

Sun. 8-10 pm, Linde Activities Center (LAC), Computer Lab (2nd floor) Richard Bowen, rsbowen A T gmail.com

 

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

·        Michael Sipser, Introduction to the Theory of Computation, Second Edition (Hardcover), Course Technology (February 15, 2005), ISBN-10: 0534950973, ISBN-13: 978-0534950972

 

·        Mordechai Ben-Ari, Mathematical Logic for Computer Science, Second Revised edition (Paperback), Springer (February 2003), ISBN-10: 1852333197, ISBN-13: 978-1852333195

 

 

 

This Outline is being revised to conform to texts.



Lecture Slides and Assignments (will be posted as each is given)


LaTex Formatting Packages


Links