PHIL 4420 / MATH 4030 - Computability and Logic

Spring 2015

Schedule

Part I - Before Break

 
Date Topic Reading Assignments
January 27 Course Overview
Propositional Logic Review 		Chapters 3, 4, and 7
presentation: Prop Logic Review 		-
January 30 Short Truth Tables presentation: Short Truth Tables

handout: Prop Logic Arguments (some valid, some invalid)

 -
February 3 Truth Trees

presentation: Truth Trees
handout: Prop Logic Arguments II (valid and invalid)

 -
February 6 Resolution and Davis-Putnam Chapter 17.4

presentation: Resolution and Davis-Putnam

 -
February 10 Natural Deduction: Fitch Chapters 5, 6, and 8, except 8.3
presentation: Formal Proofs
handout: Prop Logic Proofs (all valid)
handout: Prop Logic Proofs II (all valid) 		HW 1 due!
February 13 Existential Graphs presentation: EG -
February 17 No Class! - -
February 20 Predicate Logic Review
 Chapters 9, 10, and 11
presentation: Pred Logic Review

handout: Predicate Logic Equivalences

 HW 2 due!
February 24 Tree Method for Predicate Logic Chapters 8.3 and 18.3
presentation: Tree Method for Predicate Logic
handout: Pred Logic Arguments (some valid, some invalid)
 -
February 27 Resolution for Predicate Logic presentation: Resolution for Quantifiers -
March 3 Predicate Logic Proofs

Chapters 12 and 13
presentation: Formal Proofs for Quantifiers

handout: Pred Logic Proofs (all valid)

-
March 6

Peano Arithmetic
Non-Standard Models

 Chapter 16.4 - 16.7

presentation: Peano Arithmetic

handout: Non-Standard Models

 HW 3 due!
March 10 Proofs by Induction - -
March 13 Sets, Relations, Functions
 handout: Sets, Relations, Functions
 HW 4 due!
March 17 Cardinality, Enumerability, and Diagonalization handout: Cardinality and Enumerability -
March 20 Infinity handout: Paradoxes of Infinity HW 5 due!

Part II - After Break

March 31 Turing Machines and Turing Computability presentation: Turing Machines
software: OwenTMSimulator
handout: Instructions for use of Turing Machine Software
 -
April 3 The Halting Problem handout: Halting Problem -
April 7 The Busy Beaver Problem presentation: The Busy Beaver Problem
website: Busy Beaver Problem		 -
April 10 Abacus Machines and Abacus Computability handout: Abacus Machines
handout: Abacus Halting Function
software: Abacus Machines		 HW 6 due!
April 14 Recursive Functions ... are Abacus Computable presentation: Recursive Functions -
April 17 Recursive Sets and Relations presentation: Recursive Sets and Relations -
April 21 Turing Computable Functions are Recursive presentation: Turing Computable Functions are Recursive HW 7 due!
April 24 First-Order Logic is Undecidable
Godel's Incompleteness Theorem: Overview 		presentation: Undecidability of FOL
presentation: Godel's Incompleteness Theorem: Overview
 -
April 28 Arithmetization
 presentation: Arithmetization
 -
May 1 Arithmetical Definability
Godel's Incompleteness Theorem
Arithmetic is Undecidable 		presentation: Arithmetical Definability
presentation: The Diagonal Lemma
 		HW 8 due!
May 5 Student Presentations - -
May 8 Student Presentations - -
May 12 Student Presentations - -