SCQ1098231 - COMPUTABILITY 2023-2024
Weekly outline
-
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 3 and will be held in presence, room 2B, Campus Campus di Biologia e Biomedicina "Fiore di Botta" - 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 2, 8:30-10:30, the lesson is replaced by the "Welcome meeting", held by the Head of Studies, same room and also online [Zoom link].
The course has a tutoring activity, aimed at helping students who have difficulties, proposing exercises, discussing themes of interest. The tutor is Giacomo Stevanato (email: giacomo.stevanato.1@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.
-
- (03/10/2023) Introduction to the course. An historical view of computability. Course organisation.
-
- (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/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/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
-
- (30/10/2023)
- 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]
- (31/10/2023) Enumerating URM programs and computable functions [§4.1, §4.2]
- (30/10/2023)
-
- (06/11/2023) The diagonal method [§4.3]
- (07/11/2023) The smn theorem (or parametrisation theorem) [§4.4]
-
- (13/11/2023)
- 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]
- (14/11/2023)
- Effective operations on computable functions. Exercises. [§5.3, §6.1.1, §6.1.3, §6.1.4, §6.1.6 with slightly different approach]
-
- (20/11/2023) Exercises
- (21/11/2023) Recursive sets. Reduction. [§7.1, see also §6.1 and §9.1]
-
- (27/11/2023) Rice's theorem [§6.1.7, §6.1.8]
- (28/11/2023) Recursively enumerable sets. [§7.2.1, §7.2.2, §7.2.4, §7.2.5, §7.2.6, §7.2.13]
-
- (04/12/2023)
- 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]