Comp 230: Logic and Computability, Fall 2018 

Schedule

The schedule below is tentative and might be updated during the semester. The readings refer to the textbook (Gödel, Escher, Bach). Additional literature and handouts are available on MyCourses.

w d Day Date Content Readings HW
        Part I: Fundamentals and Formal Systems    
1 1 Tue Sep 4 Introduction to the course. Gödel's Theorem. sqrt(2) is irrational
  2 Thu Sep 6 Definition by recursion. Mathematical induction Handout 1
2 3 Tue Sep 11 Sets: Relations, functions, cardinality MyCourses
  4 Thu Sep 13 Denumerable and non-denumerable sets: Diagonalization
3 5 Tue Sep 18 Syntax. A simple formal system. The MIU system Ch. 1
  6 Thu Sep 20 Semantics. Interpretations. Infinitude of primes (Euclid) Ch. 2 1
4 7 Tue Sep 25 [Quiz 1] R.e. sets vs. recursive sets Ch. 3
  8 Thu Sep 27 Multiple interpretations, consistency, completeness Ch. 4
          Part II: Logic and Formal Arithmetic    
5 9 Tue Oct 2 Propositional logic: Semantics Handouts 2 and 2a
  10 Thu Oct 4 Propositional logic: Natural deduction Ch. 7 2
6 11 Tue Oct 9 Propositional logic: Soundness and completeness
  12 Thu Oct 11 *** First-order logic: Expressions Ch. 8 (204-214)
7 13 Tue Oct 16 [Quiz 2] First-order logic: Semantics, substitutions Handout 3
  14 Thu Oct 18 First-order logic: Proof systems, completeness  
8 15 Tue Oct 23 First-order arithmetic Ch. 8 (215-230) 3
  16 Thu Oct 25 Solution to MU puzzle. Gödel numbering Ch. 9  
9 17 Tue Oct 30 Review Handout 4  
  18 Thu Nov 1 Midterm Exam (Locations tba)  
          Part III: Computability and Incompleteness    
10 19 Tue Nov 6 Turing machines. Halting problem Handouts 5 and 6 4
  20 Thu Nov 8 Primitive recursive functions (BlooP) Ch. 13 (406-418), Hd 7
11 21 Tue Nov 13 Recursive functions (FlooP) Ch. 13 (418-430)  
  22 Thu Nov 15 Review: Turing machines, BlooP, and FlooP    
12 23 Tue Nov 20 [Quiz 3] Gödel's First Incompleteness Theorem (Part 1) Ch. 14 (438-443), Hd 8 5
  24 Thu Nov 24 Gödel's First Incompleteness Theorem (Part 2) Ch. 14 (443-449)  
13 25 Tue Nov 27 Gödel's Second Incompleteness Theorem Ch. 14 (449-460)
  26 Thu Nov 29 Undecidability. Review Ch. 17 6
  Ex tba Final Exam (Time: tba. Location: tba)    


Home Syllabus Schedule Links (c) Dirk Schlimm   8/28/2018