CS 81: Computability and Logic
Fall 2010
Course Staff
Prof. Chris Stone
,
stone@cs.hmc.edu
Sonja Bohr
Daniel Furlong
Lindsay Hall
Joshua Erlich
For quickest response, contact all of us e-mailing
cs81help@cs.hmc.edu
Selected Lecture Slides
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
.