Logic and Computability

Studiewijzer 2024/2025

Globale inhoud

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.

Studiemateriaal

Literatuur

• Velleman (2006) How to prove it. A structured approach, Second edition.

• Other literature will be made available on the canvas site of the course.

Practicummateriaal

• Extra exercises will be made available on the canvas site of the course.

Leerdoelen

• The student is able to write correct proofs for basic claims in set theory, logic, and theoretical computer science.
• The student can construct proofs induction and diagonalisation.
• The student can apply concepts of theoretical computer science like Turing Machines, complexity classes ,and set-theoretic concepts of order relations.
• The student knows central results concerning the limits of computability. They can also explain why these results hold.
• The student can explain the relevance of these results for issues in Artificial Intelligence.

Onderwijsvormen

• Hoorcollege
• Werkcollege
• (Computer)practicum
• Zelfstudie
• Begeleiding/feedbackmoment

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.

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkgroepbijeenkomsten met opdrachten geldt een aanwezigheidsplicht. De invulling van deze aanwezigheidsplicht kan per vak verschillen en staat aangegeven in de studiewijzer. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan het onderdeel niet met een voldoende worden afgerond.
  

Aanvullende eisen voor dit vak:

Presence during lectures and seminars is mandatory. Please inform the teacher in case you are absent.

Toetsing

Next to the 2 exams there are also 4 short homework assignments. The exams count 30% each, the assignments 10% 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.

Inzage toetsing

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.

Opdrachten

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.

Fraude en plagiaat

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

Weekplanning

Aanvullende informatie

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.

Contactinformatie

Coördinator

• Daniël Otten MSc