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 setsCh. 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, substitutionsHandout 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
Gödel's First Incompleteness Theorem (Part 1)
Ch. 14 (438-443), Hd 8
12
23
Tue
Nov
21
**[Quiz 3]** Gödel's First Incompleteness Theorem (Part 2)Ch. 14 (443-449)
5
24
Thu
Nov
23
Gödel's Second Incompleteness Theorem
Ch. 14 (449-460)
13
25
Tue
Nov
28
Undecidability. Tarski's Theorem
Ch. 17
26
Thu
Nov
30
Review
6
Ex
Mon
Dec
18
**Final Exam** (Time: 14:00-17:00. Location: tba)

Home | Syllabus | Schedule |
Links | (c) Dirk Schlimm 10/06/2017 |