B020989 - CALCULABILITY AND LOGIC

Italian

Introduction to recursion theory. Goedel-Church-Tarski theorems: Incompleteness, undecidability, undefinability of truth.

a) lectures notes;
b) P. Smith. An introduction to Goedel's theorems. CUP 2007

(i) Knowledge and understanding. Knowledge of the main theoretical issues and methodologies concerning recursion theory and limitative theorems. Understanding specific problems in these areas.
(ii) Applying knowledge and understanding. Applying the above knowledge and understanding though suggested exercises dealing with specific problems in the area of logic.
(iii) Making judgements.
Critical understanding of scientific contributions (articles, books) in an autonomous way.
(iv) Communication skills.
Ability to present in an appropriate way problems, solutions to problems, theories, arguments, proofs.

Background knowledge corresponding to the program of the Logic 1 course (12 CFU)/ BA level. Contact the teacher before enrolling in the course.

Lectures, plus tutorial

This course uses the E-Learning Platform MOODLE (http://e-l.unifi.it/). Students are requested to register online within the first week of the course.
Course materials (lectures notes, exercises etc.) will be available online at the Moodle page of the course.
The course requires a regular attendance (at least 2/3 of the lectures)

Oral examination (about 45 min.), typically based on two questions for each of the two parts of the program (recursion theory; limitative theorems). The student should be able to explain in a clear and appropriate language the main theoretical notions taught during the course, as well as to apply them correctly to the solution of simple exercises/problems.

Computability.
Primitive recursive functions.
Mu-recursive functions.
Kleene's normal form theorem.
First-order Peano arithmetic and subsystems.
Arithmetization of the syntax.
Representability.
Diagonalization Lemma.
Goedel's incompleteness theorems.
Church and Tarski theorems.