
Course unit
COMPUTABILITY
SCP8084818, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Core courses 
INF/01 
Computer Science 
6.0 
Course unit organization
Period 
First semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Lecture 
6.0 
48 
102.0 
No turn 
Examination board
Board 
From 
To 
Members of the board 
2 a.a. 2019/2020 
01/10/2019 
28/02/2021 
BALDAN
PAOLO
(Presidente)
BRESOLIN
DAVIDE
(Membro Effettivo)
CRAFA
SILVIA
(Supplente)
PALAZZI
CLAUDIO ENRICO
(Supplente)
RANZATO
FRANCESCO
(Supplente)

1 a.a. 2018/2019 
01/10/2018 
28/02/2020 
BALDAN
PAOLO
(Presidente)
BRESOLIN
DAVIDE
(Membro Effettivo)
CRAFA
SILVIA
(Supplente)
PALAZZI
CLAUDIO ENRICO
(Supplente)
RANZATO
FRANCESCO
(Supplente)

Prerequisites:

The course requires some familiarity with basic mathematical concepts such as relations, functions, sets, cardinality, partial orders, principles of induction.
There are no propaedeutical courses. 
Target skills and knowledge:

The aim of the course is to guide the student into some classic 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. 
Examination methods:

Written and oral exam. 
Assessment criteria:

The written test contains exercises designed to test the student's ability to use concepts and proof techniques, learnt during the course, for the solution of new problems. 
Course unit contents:

The following topics will be developed:
 Algorithms and the concept of effective procedure. Register machines (URM). Partial recursive functions. Equivalences between computational models. Universality of computational models. Church's thesis.
 Enumeration of computable functions. Existence of noncomputable functions: diagonalization techniques. The parameter theorem. Universal programs.
 Decidable, undecidable and semidecidable problems. Undecidability of the halting problem. Reduction techniques. Other undecidable problems.
 Recursive and recursively enumerable sets. Rice and RiceShapiro theorems.
 Functionals. Recursive definitions. Partial orderings, monotone functions and fixed points. Recursive functional. MyhillSheperdson's theorem. First recursion theorem. Second recursion theorem. 
Planned learning activities and teaching methods:

The course consists of lectures and exercises. 
Additional notes about suggested reading:

Web page:
http://www.math.unipd.it/~baldan/Computabilita 
Textbooks (and optional supplementary readings) 

Nigel Cutland, Computabiliy: An Introduction to Recursive Function Theory. : Cambridge University Press, 1980.

Innovative teaching methods: Teaching and learning strategies
 Lecturing
 Problem based learning
 Story telling
 Problem solving
Innovative teaching methods: Software or applications used
 Moodle (files, quizzes, workshops, ...)
 Latex
Sustainable Development Goals (SDGs)

