Computability

Master's Degree in Computer Science - University of Padua
Academic Year 2023/2024

Paolo Baldan

Objectives

The aim of the course is to guide the student into some classical themes in the theory of computability, completing and deepening the knowledge acquired at undergraduate level. Starting from a mathematical analysis of the intuitive concept of an effective procedure, the class of effectively computable functions is formally introduced, and a theory of undecidability and recursion is developed.

There is a moodle page where additional material about the course (notes, exercised, etc) can be found.

Program

The course consists of 48 hours of lessons and it will develop the following themes:
  1. Algorithms and the concept of effective procedure. Register machines (URM). Partial recursive functions (substitution, recursion, minimalization). Functional computational models. Equivalences between computational models. Universality of the models of computation. Church's thesis.
  2. Enumeration of computable functions. Existence of non computable functions: the diagonalization method. The parameter theorem. Universal programs.
  3. Decidable, undecidable and semi-decidable problems. Undecidability of the halting problem. Method of reduction. Other examples of undecidable problems.
  4. Recursive and recursively enumerable sets. Rice's and Rice-Shapiro's theorems.
  5. Functionals. Recursive definitions. Partial orders, monotone functions and fixed points. Recursive functionals. Relation between continuity and recursiviness. Myhill-Shepherdson's theorems`. First recursion theorem. Second recursion theorem.
A detailed description of what is presented in the course follows. For each topic you'll find numbers which refers to the official textbook, according to the scheme chapter.paragraph, pages.

Schedule

The course is part of the Master's Degree in Computer Science, University of Padua. It is held in Semester I for the Academic Year 2022/2023, It will start on 03.10.2022, room Luf1 with the following schedule:

Exams

The dates of the exams can be found the following link.

The exam consists of a written test, requiring the solution of some exercises. The exam is closed-book: you will not be allowed to consult books or any other material. An oral exam is required only for getting the highest grade (30 cum laude). This means that students obtaining a grade between 18 and 30 in the written test can simply keep their grade. The (optional) oral exam must be taken in the same session of the written exam. Once taken, it is part of the exam and it contributes positively or negatively to the overall grade. After each written test, student can (and are suggested to, especially if they did not pass) consult the correction of their exam. A collection of exercises from exams of the previous academic years can be found at the following links: with solutions here and without solutions here

Material

We will use the following textbook