Corso: SCQ1098231 - COMPUTABILITY 2022-2023

SCQ1098231 - COMPUTABILITY 2022-2023 - PROF. PAOLO BALDAN

This section contains material for the Computability course. For a general description and more information about the course, please refer to the corresponding web page.

In the description of the topics discussed during the the lessons, you'll find references to the official textbook in the form §chapter.paragraph.subparagraph

A collection of exam exercises with solutions is available at the [link]. The same exercises are also available without solution at the [link].

Lessons will start on Oct 4 and will be held in presence, room Luf1 - link on Gmaps. For helping students who did not yet make it to reach Padua some material (mostly, lessons recordings and other online material) will be made available.

Note: On Monday Oct 3, 8:30-10:30, the lesson is replaced by the "Welcome meeting", in presence in room Luf1 and on zoom at the following [link].

The course has a tutoring activity, aimed at helping students who have difficulties, proposing exercises, discussing themes of interest. The tutor is Riccardo Borsetto (email: riccardo.borsetto@studenti.unipd.it). Details about the activity can be found on the corresponding Fiup Group.

Some unofficial notes for the course can be found at the following link (the PDF file will be updated regularly). They are sketchy notes, produced with the help of some students. They can contain errors or inaccuracies (in case you find some, please report them). They are intended as a support for students for understanding what have been discussed in the lessons. They do not replace the official book (Nigel Cutland ``Computability. An Introduction to Recursive Function Theory''), on which they are heavily based.

3 ottobre - 9 ottobre

(03/10/2022) Welcome Meeting for the Master's Degree in Computer Science
(04/10/2022) Introduction to the course. An historical view of computability. Course organisation.

10 ottobre - 16 ottobre

(10/10/22) Effective procedures and computable functions. Relations, functions, sets and cardinality. Existence of non-computable functions.
(11/10/22) URM-computability. The class C of URM-computable functions. Examples. [§1.2, §1.3]

17 ottobre - 23 ottobre

(17/10/2022)

Exercises on some variants of the URM machine
Decidable predicates. [§1.4]
Computability on domains different from the natural numbers. [§1.5, §3.6]

(18/10/2022)

Generating computable functions: Notation. Closure under generalised composition (Substitution) [§2.1, §2.2, §2.3]
Primitive recursion and examples [§2.4]

24 ottobre - 30 ottobre

(24/10/2022) Generation of computable functions

Primitive recursion and examples [§2.4]
Definition by cases. Algebra of Decidability. Bounded sums and products. Bounded quantification [§2.4.6, §2.4.7, §2.4.10]
Bounded minimalisation [§2.4.12, §2.4.13, §2.4.14, §2.4.15]

(25/10/2022) Generation of computable functions

Unbounded minimalisation [§2.5]
Computability of the inverse function. Finite functions and their computability.
Partial recursive functions [§3.1, §3.2, §3.7]
- Definition
- The class of partial recursive functions coincide with the class of URM-computable functions

31 ottobre - 6 novembre

7 novembre - 13 novembre

(07/11/2022)

Proof of the fact that the class of partial recursive functions coincide with the class of URM-computable functions
Primitive recursive funcions. [§3.3]
Ackermann's functions: total, computable and not primitive recursive [partially in §2.5.5]

(08/11/2022) Enumerating URM programs and computable functions [§4.1, §4.2]

14 novembre - 20 novembre

(14/11/2022) The diagonal method [§4.3]
(15/11/2022) The smn theorem (or parametrisation theorem) [§4.4]

21 novembre - 27 novembre

(21/11/2022)

Universal function: definition and computability [§5.1, Appendix of §5]
computability of the inverse function, undecidability of the halting problem and of totality [§5.1]

(22/11/2022)

Effective operations on computable functions. Exercises. [§5.3, §6.1.1, §6.1.3, §6.1.4, §6.1.6 with slightly different approach]

28 novembre - 4 dicembre

(28/11/2022) Exercises
(29/11/2022) Recursive sets. Reduction. [§7.1, see also §6.1 and §9.1]

5 dicembre - 11 dicembre

(05/12/2022) Rice's theorem [§6.1.7, §6.1.8]
(06/12/2022) Recursively enumerable sets. [§7.2.1, §7.2.2, §7.2.4, §7.2.5, §7.2.6, §7.2.13]

12 dicembre - 18 dicembre

(06/12/2021)

Reducibility and r.e. sets [§9.1.3]
Alternative characterisation of r.e. sets [§7.2.3, §7.2.7]
Introduction to Rice-Shapiro's theorem [§7.2.16]

(07/12/2021)

Rice-Shapiro's theorem. Proof, examples, countexample to the converse implication [§7.2.16]

19 dicembre - 25 dicembre

(13/12/2021) Recursive functionals (recursive operators, in the book). Myhill-Shepherdson Theorem. First recursion theorem [§10.1, §10.2, §10.3, without proofs]
(14/12/2021) Second recursion theorem [§11.1, §11.2]

(09/01/2023) Exercises
(10/01/2023) Exercises

16 gennaio - 22 gennaio

(16/01/2023) Exercises

SCQ1098231 - COMPUTABILITY 2022-2023

Attività settimanale