CS 81: Computability and Logic
Fall 2010

Course Staff

• Prof. Chris Stone, stone@cs.hmc.edu
• Sonja Bohr
• Daniel Furlong
• Lindsay Hall
• Joshua Erlich

• Introduction: Background, Inductive Definitions, Structural Induction
• Constructive Math; Temporal Logic; Linear Logic
• Hoare Logic (Handout)
• Regular languages, Lecture 1, Lecture 2, Lecture 3.
• Nonregular Languages
• Context-Free-Grammars
• PDAs and Parsing, Lecture 1, Lecture 2
• Intro to Turing Machines
• Uncomputability
• Reductions
• PCP
• Recursion Theorem; Counter Machines; Partial Recursive Functions
• Logic, Decidability, and Incompleteness

Handouts

• Syllabus

Homework Assignments

• Assignment 1; Prof's LaTeX source (won't run through directly, but there may be useable bits); Sample solution on Sakai.
• Assignment 2; Sample solution on Sakai.
• Assignment 3; Sequent Calculus and sample solution are on Sakai.
• Assignment 4; Sample solution on Sakai.
• Assignment 5; Sample solution on Sakai.
• Assignment 6; Sample solution on Sakai.
• Assignment 7; Sample solution on Sakai.
• Assignment 8.
• Assignment 9; Sample solution on Sakai.
• Assignment 10.
• Assignment 11; Sample solution on Sakai.
• Assignment 12; Sample solution on Sakai.