| |
Intstructor: Dr Eric Pacuit
Class Meetings: Wednesdays 11 - 13, Fridays 11 - 13
Classroom: Wednesdays P.015A, Fridays P.015 B
Course Language: English
Intended Audience: M.Sc. students of Logic and Mathematics
Prerequisites: This course assumes mathematical maturity and knowledge about first-order logic.
Content of the Course: This lecture course will cover the basics of recursion theory (models of computation, limitative theorems) and discuss the connections between recursion theory and the foundations of mathematics (Gödel's Incompleteness Theorem). After that, recursion-theoretic hierarchies (Turing degrees) will be introduced.
Textbook: Barry Cooper, "Computability Theory" (Chapters 1-10).
Evaluation: There will be 11 homework assignments each worth 6 points and one worth 10 points, for a total of 76 points. The final grade will depend on the total number of homework points.
Grades: Grades will be posted as soon as possible. I expect to be finished by the first week of January. Please send your final assignments to me as soon as possible.
|
|
| |
Course Schedule
(subject to change) |
Week |
Date |
Topics |
Homework Sets |
Period A (weeks 1-8) |
| 1 |
Sep. 7 |
1.1-1.4, 2.1, 2.2 |
Due Sep. 14
Problem Set 1 |
| Sep. 9 |
Practice session |
Practice Problems 1
Some additional notes.
|
| 2 |
Sep. 14 |
2.2, 2.3 |
Due Sep. 21
Exercises 2.2.12, 2.3.6, 2.3.7 |
| Sep. 16 |
Practice session |
Practice session canceled |
| 3 |
Sep. 21 |
2.4, 2.5 |
Due Sep. 28
Problem Set 3 |
| Sep. 23 |
Practice session |
Solutions to HW 1, 2.4.15, 2.5.3 |
| 4 |
Sep. 28 |
4.1 - 4.3 |
Due Oct. 5
Problem Set 4 |
| Sep. 30 |
Practice session |
Handout |
| 5 |
Oct. 5 |
4.4, 4.5, 5.1, 5.2 |
Due Oct. 12
Problem Set 5 |
| Oct. 7 |
Practice session |
Solutions to HW, 5.2.12, 5.2.13, 5.2.15, 5.2.17, 5.2.19 |
| 6 |
Oct. 12 |
5.2, 5.3, 5.4 |
Due Oct. 21
Problem Set 6
Notes on Problem Set 6 |
| Oct. 14 |
5.4, 3.1, 3.2 |
|
| 7 |
Oct. 19 |
6.1, 6.2, 6.3 |
Due Nov. 2
No Homework |
| Oct. 21 |
Practice session |
Chapter 3 |
| 8 |
Oct. 26 |
No Class Exam Week |
|
Oct. 28 |
No Class Exam Week |
|
Period B (weeks 9-16) |
| 9 |
Nov. 2 |
7.1, 7.2 |
Due Nov. 9
Homework 7 |
| Nov. 4 |
Practice session |
6.2.7, 6.2.8, 7.1.7, 7.1.8, 7.2.13 |
| 10 |
Nov. 9 |
7.2, 7.3, 8.1 |
Due Nov. 16
7.2.10, 8.1.3, 8.1.4, 8.1.7 |
| Nov. 11 |
8.1, 8.2/Practice Session |
8.1.6, 8.1.11, 8.1.17 |
| 11 |
Nov. 16 |
9.1, 9.2, 9.3 |
Due Nov. 23
9.1.2., 9.1.3., 9.1.6., 9.2.13., 9.3.4
(2 points each) |
| Sep. 18 |
Practice session |
9.2.12., 9.3.3., 9.3.5 |
| 12 |
Nov. 23 |
10.1, 10.2 |
Due Nov. 30
10.3.3, 10.3.4, 10.3.6 |
| Nov. 25 |
Practice session |
10.1.4, 10.2.6, 10.3.8, 10.3.9 |
| 13 |
Nov. 30 |
10.4 |
Due Dec. 7
10.3.10, 10.4.9, 10.4.22 |
| Dec. 2 |
Practice session, 10.5 (up to Post's Theorem) |
10.4.8, 10.4.10 - 10.4.12, 10.4.16, 10.4.20, 10.4.21, 10.5.3, 10.5.4 |
| 14 |
Dec. 7 |
10.5, 10.6
| Due Dec. 18
Homework 12 (10 points) |
| Dec. 9 |
10.6, 11.1 |
|
| 15 |
Dec. 16 |
11.1, 11.6 |
|
| Dec. 18 |
11.1, 11.6 |
|
|
|