COMPUTABILITY

Knowledge and understanding: students will acquire knowldege relative to the formalization of the notion of algorithm, by means of of Unlimited Register Machines (URM), examples of non-computable functions and undecidable predicates will be exhibited, the notion of decidability will be generalized to that of partial decidability and students will learn various techniques (such as the technique of reduction. the Theorems of Rice and of Rice-Shapiro, and the Theorem s-m-n) to verify whether a given predicate is partially decidable or not.

Applying knowledge and understanding:  students will acquire the ability to construct non-computable functions under various constraints using diagonalization and to verify whether a given predicate is partially decidable or not.

Making judgments: students will be able to evaluate, even informally, the status of (semi-)decidability of a given computational problem.

Communication skills: Students will acquire the communication and expressive skills necessary to present and discuss algorithmic problems, including with non-expert interlocutors.

Learning skills: students will have the ability to adapt the knowledge acquired also in new contexts and to advance his/her knowledge through the consultation of specialist sources in the computability field.

Classroom-taught lessons

Should teaching be delivered in mixed mode or remotely, some adjustments may be required compared to the above, in accordance with the organization and contents set out in the syllabus.

Information for students with disabilities and / or SLD

To guarantee equal opportunities and in compliance with the laws in force, interested students can ask for a personal interview in order to plan any compensatory and / or compensatory measures, based on the didactic objectives and specific needs. It is also possible to contact the referent teacher CInAP (Center for Active and Participated Integration - Services for Disabilities and / or SLD) of our Department, prof. Patrizia Daniele.

Class attendance is not mandatory, but it is strongly recommended for a full understanding of the course topics and the problem-solving techniques presented.

Computable functions: algorithms, effective procedures. URM model: Unlimited Register Machines. URM-computable functions. Decidable predicates and problems. Computability in other domains.

Generation of URM-computable functions: basic functions, composition or substitution, recursion, minimalisation.

Church-Turing's thesis: Other approaches to computability. Primitive recursive functions and general recursive functions. Turing machines. (Post and Markov systems.)

Enumeration of computable functions. Enumeration of URM-programs. The diagonal method. The s-m-n theorem

Universal programs: universal functions and universal programs (and applications). Effective operations on computable functions.

Decidability, undecidability and partial decidability: Undecidable problems in computability and in other areas of mathematics. Rice's theorem. Partial decidable problems.

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge, UK, 1986. [Main textbook]

2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Recommended reading]

The following criteria are generally applied for the assignment of the final grade:

Not approved: the student has not yet acquired the basic concepts and is unable to adequately solve the exercises.

18–23: the student demonstrates an essential knowledge of the basic concepts; exposition and ability to connect topics are limited, but the student manages to solve simple exercises.

24–27: the student demonstrates a good knowledge of the course contents, presents them clearly and connects them appropriately; exercises are solved with few errors.

28–30 with honors: the student has acquired a complete knowledge of the contents, presents them with clarity and critical insight, and solves the exercises accurately and without errors.

Students with disabilities and/or specific learning disorders (DSA) must contact the instructor, the CInAP representative of the DMI (Prof. Daniele), and CInAP sufficiently in advance of the exam date to notify their intention to take the exam with the appropriate compensatory measures.

Sample Exam Questions (for illustrative purposes only)

1. Determine whether a given function is computable.

2. State and prove the parameterization theorem.

3. Prove the existence of a total computable function $s : N -->N such that W_{s(n)} and E_{s(n)} are equal to given sets, for each natural number n.

4. State Rice’s theorem and the Rice-Shapiro theorem.

5. Prove Rice’s theorem.

6. Analyze the decidability and semi-decidability of a given predicate and its negation.

7. Use the diagonalization technique to prove the existence of a total non-computable function satisfying certain constraints.

8. Prove that if P(x) is a unary semi-decidable predicate, then there exists a decidable predicate R(x, y) such that P (x) <==> (∃y)R(x,y).

Note: the exercises listed above are only examples; the exam may also include questions on other topics covered in the course.