Computability
Master's Degree in Computer Science  University of Padua
Academic Year 2021/2022
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:
 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.
 Enumeration of computable functions. Existence of
non computable functions: the diagonalization method. The
parameter theorem. Universal programs.
 Decidable, undecidable and semidecidable problems.
Undecidability of the halting problem. Method of reduction. Other
examples of undecidable problems.
 Recursive and recursively enumerable sets.
Rice's and RiceShapiro's theorems.
 Functionals. Recursive definitions. Partial orders, monotone
functions and fixed points. Recursive functionals. Relation
between continuity and recursiviness. MyhillShepherdson'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
noncomputable (Introduction, 1.1, p. 19).

URMcomputability. The class C of URMcomputable
functions. Examples of URMcomputable functions.
the transfer instruction (1.2, 1.3, pp. 922).

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, 2223).
Computability on other domains (1.5, 2324).

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 smn 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)

RiceShapiro 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 2021/2022,
It will start on the 27.09.2021, 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 closedbook: 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.
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