COMPUTABILITY 2024-2025 - SCQ1098231
Aperçu des semaines
-
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
Lessons will start on September 30 and will be held in presence, room LuF1. 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.
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.
A collection of exam exercises with solutions is available at the [link]. The same exercises are also available without solution at the [link].
TUTOR
The course has a tutoring activity, aimed at helping students who have difficulties, proposing exercises, discussing themes of interest. The tutor is Gabriel Rovesti (email: gabriel.rovesti@studenti.unipd.it). Details about the activity can be found at the following [link] on the corresponding Fiup Group.
Note: On Monday Sep 30, 8:30-10:30, the lesson is replaced by the "Welcome meeting", same room and also online.
-
- (30/09/2024) Welcome Meeting for the Master's Degree in Computer Science
- (01/10/2024) Introduction to the course. An historical view of computability. Course organisation.
-
- (07/10/24) Effective procedures and computable functions. Relations, functions, sets and cardinality. Existence of non-computable functions.
- (08/10/24) URM-computability. The class C of URM-computable functions. Examples. [§1.2, §1.3]
-
- (14/10/2024)
- Exercises on some variants of the URM machine
- Decidable predicates. [§1.4]
- Computability on domains different from the natural numbers. [§1.5, §3.6]
- (15/10/2024)
- 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]
- (29/10/2024) 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 [statement and some ideas]
-
- (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]
- Proof of the fact that the class of partial recursive functions coincide with the class of URM-computable functions
- (31/10/2023)
- Enumerating URM programs and computable functions [§4.1, §4.2]
- Enumerating URM programs and computable functions [§4.1, §4.2]
- (30/10/2023)
-
- (11/11/2024) The diagonal method [§4.3]
- (12/11/2024) The smn theorem (or parametrisation theorem) [§4.4]
-
- (18/11/2024)
- 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]
- (19/11/2024)
- Effective operations on computable functions. Exercises. [§5.3, §6.1.1, §6.1.3, §6.1.4, §6.1.6 with slightly different approach]
-
- (25/11/2024) Exercises
- (26/11/2024) Recursive sets. Reduction. [§7.1, see also §6.1 and §9.1]
-
- (02/12/2024) Rice's theorem [§6.1.7, §6.1.8]
- (03/12/2024) Recursively enumerable sets. [§7.2.1, §7.2.2, §7.2.4, §7.2.5, §7.2.6, §7.2.13]
-
- (09/12/2024)
- 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]
- (10/12/2024)
- Rice-Shapiro's theorem. Proof, examples, countexample to the converse implication [§7.2.16]
- Rice-Shapiro's theorem. Proof, examples, countexample to the converse implication [§7.2.16]
- (09/12/2024)