6 EC
Semester 1, period 1
5082LOCO6Y
Looking at the amazing speed of progress in informatics and artificial intelligence, one is easily lured into the belief that everything is possible in these areas; maybe not now, but certainly at some point in the not that far of future. The central goal that we will work towards in this class is proving that there are actually very hard limits to what a computer can do: not every function is computable. For this we will introduce Turing Machines for a precise understanding of computability. With this newfound insight, we will also prove that predicate logic, which seems to be a still rather simple formal language, is undecidable: whether a statement in predicate logic is valid is not in general computable.
But before we can get to these sophisticated proofs, we need to do some groundwork. First of all, we have to hone our skills for writing and understanding mathematical proofs. We will start with very simple proofs about basic set theoretic notions and then add more and more complexity. In particular you will learn to do proofs by induction and diagonalisation. Induction allows us to prove strong universal claims about recursive structures, while diagonalisation helps us find limits in self referential structures.
Velleman (2006) How to prove it. A structured approach, Second edition.
Other literature will be made available on the canvas site of the course.
Extra exercises will be made available on the canvas site of the course.
In the lectures we will introduce the central concepts and results of this class and discuss their applicability to AI. In the seminars we will follow the book and practise proving more and more complex statements about set theoretic notions. During the selfstudy hours you will prepare for the lectures and seminars, but also work through some parts of the book by yourself. The four assignments are specifically designed to test the material not covered in class. The practicum gives you the opportunity to ask questions and work on the assignments. In the weeks where the exams take place there is an extra meeting for any questions you might have.
|
Activiteit |
Uren |
|
|
Deeltoets |
2 |
|
|
Hoorcollege |
12 |
|
|
Tentamen |
2 |
|
|
Werkcollege |
14 |
|
|
Practicum |
12 |
|
|
Zelfstudie |
122 |
|
|
Begeleiding/feedbackmoment |
4 |
|
|
Totaal |
168 |
(6 EC x 28 uur) |
Programme's requirements concerning attendance (TER-B Article B-4.10):
| Item and weight | Details |
|
Final grade | |
|
40% Deeltoets | Mandatory |
|
40% Tentamen | Mandatory |
|
5% Homework Assignment 1 | |
|
5% Homework Assignment 2 | |
|
5% Homework Assignment 3 | |
|
5% Homework Assignment 4 |
| exam | material covered |
| exam 1 (deeltoets) | Diagonalisation, Chapter 2.3, 3.1-3.6 and 4.1-4.5 of How To Prove It, and the additional material covered in the first 3 lectures. |
| exam 2 (eindtoets) |
Induction (see .61-6.2 of How To Prove It, but also the material discussed in class), and the additional material covered in the last 3 lectures. |
Next to the 2 exams there are also 4 homework assignments. The exams count 40% each, the assignments 5% each for the final grade. In order to pass the class the student has to get an average of at least 5,5 and pass the exams with an average of at least 5,5.
The homework assignments and the first written exam will be handed back during class and can be discussed directly with the teacher/assistent. For an inspection of the second written exam the student can make an appointment with the teachers.
The students have to submit four homework assignments. These assignments should be handwritten and have to be handed in in week 2, 3, 6 and 7. The students have to work on these assignments individually. The assignments will be graded. They will be handed back and discussed in the practicum session.
The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl
| Weeknummer | Onderwerpen | Studiestof |
| 1 |
Computability and Turing Machines; Basic Proof Strategies. |
Chapter 3 of "How to prove it"; Lecture Slides and Seminar slides; Homework on Canvas. |
| 2 |
Proofs about Relations and Functions; Computable Functions; Encodings; Cardinalities. |
Lecture Slides and Seminar slides; Homework on Canvas. |
| 3 | Diagonalisation; Cantor's Theorem; The Halting Problem. | Lecture Slides and Seminar slides; Homework on Canvas. |
| 4 | Additional Exercises and Midterm Exam | |
| 5 | Proofs by Induction; Reductions. | Sections 6.1 and 6.2 of "How to prove it"; Lecture Slides and Seminar slides; Homework on Canvas. |
| 6 | Strong induction; Introduction to Complexity Theory. | Lecture Slides and Seminar slides; Homework on Canvas. |
| 7 | Undecidability of Predicate Logic | Lecture Slides and Seminar slides; Homework on Canvas. |
| 8 | Final exam |
In order to follow this class you need to have successfully finished the Introduction to Logic or a similar course. If you are not sure whether you fulfill the entry requirements of this class, please contact the teachers.
Please make sure that you refresh your knowledge of the material covered in the Introduction to Logic before the start of this course. There will be little room to do so after the course has started. Look in particular at Natural Deduction and the notions/notation from set-theory that were introduced in that class.