6 EC
Semester 1, periode 1
5082LOCO6Y
Looking that the amazing speed with which progress is made in informatics and artificial intelligence, one is easily lured into the belief that in these areas everything is possible; maybe not now, but certainly at some not that far point in the 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 the Turing Machine perspective on what computability means. With this result in our pockets we will then also prove that predicate logic, which seems to be still a rather simple formal language, is undecidable: whether an argument in predicate logic is valid or not is not in general computable.
But before we can get to these sophisticated proofs, we need to do some work. 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. This is a techniques that allows you to prove strong universal claims about recursive structures.
But we also have to do some conceptual work. We need to understand the proof strategy of proof by diagonalisation. We will start studying this technique by looking at a results concerning infinity: Cantor's theorem and the apply it to computability.
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 |
12 |
|
|
Practicum |
12 |
|
|
Zelfstudie |
124 |
|
|
Begeleiding/feedbackmoment |
4 |
|
|
Totaal |
168 |
(6 EC x 28 uur) |
Aanwezigheidseisen opleiding (OER-B):
Aanvullende eisen voor dit vak:
Presence during lectures and seminars is mandatory. Please inform the teacher in case you are absent.
| Onderdeel en weging | Details |
|
Eindcijfer | |
|
1 (10%) homework assignment 1 | |
|
1 (10%) homework assignment 2 | |
|
3 (30%) Deeltoets | |
|
1 (10%) homework assignment 3 | |
|
1 (10%) homework assignment 4 | |
|
3 (30%) Tentamen |
| exam | material covered |
| exam 1 (deeltoets) | 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) | Mathematical 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. |
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 teacher.
The students have to submit four homework assignments. These assignments have to be handed in at the end of week 1, 2, 5 and 6. The students have to work on these assignments individually. The assignments will be graded. They will be handed back and discussed the week thereafter in the practicum session.
Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: http://student.uva.nl
| Weeknummer | Onderwerpen | Studiestof |
| 1 |
computability and Turing machines,basic proof stategies |
ch. 3 of "How to prove it" and material on canvas |
| 2 |
Ackerman and Busy Beaver,proofs about relations, order relations |
ch. 4.1-4.4 of "How to prove it" and material on canvas |
| 3 | Cardinality and Cantor's Theorem | ch. 4.5 of "How to prove it" and material on canvas |
| 4 | midterm exam | |
| 5 | The halting problem, proof by induction | ch. 6.1 of "How to prove it" and material on canvas |
| 6 | Introduction to complexity, strong induction, soundness of propositional logic | ch. 6.2 of "How to prove it" and material on canvas |
| 7 | Kolmogorov complexity, undecidability of first order logic | material on canvas |
| 8 | final exam |
Het rooster van dit vak is in te zien op DataNose.
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 teacher.
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.
Hieronder vind je de aanpassingen in de opzet van het vak naar aanleiding van de vakevaluaties.
The students were very happy with the course last year, so there will be only minor changes this year. Based on the feedback we got from the students I made the following adaptations.
- There will be more questions on material covered in the lectures in the exams.
- I will discuss with the students during the first lecture whether the deadline for the assignments should be moved to Friday.
- In the second part of the class there will be an introduction to complexity to connect the content of this class better to other parts of the BA programme. We will also discuss Kolmogorov complexity as an application.
Office hour: Thursday, 2pm-3pm in L6.32.