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.

• Historical remarks. From logic to computability to modern computer science. Organization of the course. [Slides]
• Effective procedure and computable function. Characteristics of an algorithm and of a computational model. Existence of functions non-computable (Introduction, 1.1, p. 1-9).
• URM-computability. The class C of URM-computable functions. Examples of URM-computable functions. the transfer instruction (1.2, 1.3, pp. 9-22).
• Exercise: invariance of the class of computable functions when replacing the transfer instruction T(m,n) with the exchange instruction T_s(m,n).
  Exercise: what can one compute without the jump instruction?
• Decidable predicates (1.4, 22-23). Computability on other domains (1.5, 23-24).
• Generation of computable functions: Basic functions (2.1). Composition of programs (2.2). Generalized composition (2.3). Primitive recursion (2.4). Bounded minimalization (2.5).
• Encoding of pairs and tuples. Considerations on recursion. Minimalization (2.5). Exercises on minimalization.
• Other approaches to computability. Church's thesis. Partial recursive functions R. (3.1, 3.2, 3.3, 3.7)
  Implementation in Haskell of the operators for recursive partial functions and of the universal function, realised by a student.
• Primitive recursive functions PR. The Ackermann function (totality and hints to computability). (2.5) The Ackermann Function is not primitive recursive.
  (Animation of the Ackermann function)
• Enumeration of URM programs (4.1)
• Enumeration of computable functions (4.2) The diagonal method (4.3)
• Kleene's s-m-n theorem (4.4)
• Universal function (5.1, appendix of chap. 5)
• Exercises and applications of the universal function (5.2, excluding Theorem 2.2, and 5.3). Undecidability of the halting problem (a video on the topic).
• Recursive sets and reduction (6.1 and 7.1)
• Rice's theorem (6.1)
• Recursively enumerable sets (7.2) and semidecidable predicates (6.6)
• Rice-Shapiro theorem (6.6)
• First recursion theorem (general ideas - 10.1, 10.3)
• Second recursion theorem (11.1, 11.2)

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 2024/2025, It will start on 29.09.2024, room Luf1 with the following schedule:

• Mon (8:30 - 10:15)
• Tue (8:30 - 10:15)

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, the oral becomes part of the overall assessment and may positively or negatively affect the final grade. The oral exam primarily covers the theoretical aspects (definitions, proofs, constructions discussed during the course). 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

• Nigel Cutland "Computability. An Introduction to Recursive Function Theory"
  Cambridge University Press