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 setsCh. 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, substitutionsHandout 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 |