28101 - Logic (1) (2nd cycle)

Learning outcomes

At the end of the course, students are supposed to become acquainted with fundamental knowledge on the metatheory of some selected formal systems concerning crucial topics in Logic, such as validity, completeness, decidability, and possibly referring to well known limiting results

Course contents

COMPUTABILITY AND PROOF

The course will explore the concepts of computability and algorithms, including their relation to logical proof methods. The concepts of computability and algorithms are fundamental in contemporary society, and we are constantly subjected to computational processes, performed by human or electronic agents. However, not everyone understands the concept of "computable," or can distinguish in principle between computably solvable problems and problems that are not.

The aim of this course is to provide the conceptual tools for a deeper understanding of the concept of computability, both technically and philosophically.  

Topics covered:

- Turing machines

- Recursive functions

- The Church-Turing Thesis

- Recursive and recursively enumerable sets

- Decidable and undecidable problems

- The resolution method

- Computability on the continuum: problems and methods

Readings/Bibliography

Handout provided by the teacher.

 

Non-attending students will also have to study the first two chapters of the book "La computabilità: algoritmi, logica, calcolatori", di M. Frixione, D. Palladino, Carocci Editore.

Teaching methods

Lessons in classroom with electronic blackboard. Lessons will be recorded and uploaded on line.

Assessment methods

The final exam will consist in an oral test, in which students are asked to prove their correct comprehension of the notions dealt with during the course, by oral explanation and also by written reconstruction of the fundamental definitions, results and proofs. 

 

To take the exam, students can register for the regular sessions scheduled by the Teacher or arrange individual sessions. Regular exam sessions will take place approximately every two months starting in April 2026 (June, September, November, January, March), and the dates will be set approximately one month before the exam.

 

Assessment criteria and thresholds of evaluation:

30 cum laude: Excellent as to knowledge, terminology and critical expression.

30: Excellent, knowledge is complete, well articulated and mostly correctly expressed, although with some slight faults.

27-29: Good, knowledge comprehensive and satisfactory, essentially correct expression.

24-26: Fairly good, knowledge present in significant points, but not complete and not always expressed with correctness.

21-23: Sufficient, knowledge is sometimes superficial, but the guiding general thread is included. Expression and articulation incomplete and often not appropriate

18-21:.Almost sufficient, but knowledge present only on the surface. The guiding principle is not included with continuity. The expression and articulation of the speech show important gaps.

<18: Not sufficient, knowledge absent or very incomplete, lack of guidance in discipline, expression seriously deficient. Exam failed.

Teaching tools

- Electronic whiteboard. 

- Video projector.

- Lessons recording.

Office hours

See the website of Guido Gherardi