First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
COMPUTER SCIENCE
Course unit
COMPUTABILITY
SCP8084818, A.A. 2019/20

Information concerning the students who enrolled in A.Y. 2019/20

Information on the course unit
Degree course Second cycle degree in
COMPUTER SCIENCE
SC1176, Degree course structure A.Y. 2014/15, A.Y. 2019/20
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination COMPUTABILITY
Website of the academic structure http://informatica.scienze.unipd.it/2019/laurea_magistrale
Department of reference Department of Mathematics
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge PAOLO BALDAN INF/01

ECTS: details
Type Scientific-Disciplinary 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

Calendar
Start of activities 30/09/2019
End of activities 18/01/2020
Show course schedule 2019/20 Reg.2014 course timetable

Examination board
Board From To Members of the board
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)

Syllabus
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 non-computable 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 Rice-Shapiro theorems.
- Functionals. Recursive definitions. Partial orderings, monotone functions and fixed points. Recursive functional. Myhill-Sheperdson'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. Cerca nel catalogo

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)
Quality Education