# COMPUTABILITY

**Academic Year 2023/2024**- Teacher:

**Domenico CANTONE**

## Expected Learning Outcomes

*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 judgements*: students will be able to evaluate even informally the status of (semi-)decidability of a given computational problem.

*Communication skills*

*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.

## Course Structure

Classroom-taught lessons

Should teaching be offered in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.

Information for students with disabilities and / or SLDTo 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. Filippo Stanco.

## Required Prerequisites

Elements of discrete mathematics

Intuitive concept of algorithm

Elements of mathematical logic

## Attendance of Lessons

## Detailed Course Content

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.

## Textbook Information

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]

## Course Planning

Subjects | Text References | |
---|---|---|

1 | Computable functions: algorithms, effective procedures. URM model: Unlimited Register Machines. URM-computable functions. Decidable predicates and problems. Computability on other domains. | Chapter 1.1-1.5 of 1) and integrative handouts. |

2 | Generation of URM-computable functions: Initial functions. Composition. Recursion. Minimalisation. | Chapter 2.1-2.5 of 1) and integrative handouts. |

3 | Church-Turing thesis: Other approach to computability. Primitive recursive functions and general recursive functions. Turing machines. | Chapters 3.1-3.4, 3.6 e 3.7 of 1) and integrative handouts. |

4 | Post-systems and Markov- systems. | Chapter 3.5 of 1) |

5 | Enumeration of computable functions: enumeration of URM-programs. Diagonal method. S-m-n theorem. | Chapters 4.1-4.4 of 1) and integrative handouts. |

6 | Universal programs: universal functions and programs (with applications). Effective operations on computable functions. | Chapter 5.1-5.3 of 1) and integrative handouts. |

7 | Undecidable problems in computability. | Chapter 6.1 of 1) and integrative handouts. |

8 | Undecidable problems in other areas of mathematics. | Chapter 6.2-6.5 of 1) |

9 | Semi-decidable problems | Chapter 6.6 of 1) and integrative handouts. |

10 | Recursive sets and recursively enumerable sets. Rice and Rice-Shapiro theorems. | Chapter 7.1-7.2 of 1) and integrative handouts. |

## Learning Assessment

### Learning Assessment Procedures

The final exam is essentially written. The verbalization may be preceded by a short discussion on the written assignment and, in doubtful cases, by a short oral test.

Verification of learning can also be carried out electronically, should the conditions require it.