Comp 230: Logic and Computability, Fall 2017 

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


Home Syllabus Schedule Links (c) Dirk Schlimm   11/08/2017