# Coursebooks

## Gödel and recursivity

English

#### Remarque

Cours donnés en alternance tous les deux ans (pas donné en 2019-20)

#### Summary

Gödel incompleteness theorems and mathematical foundations of computer science

#### Content

Gödel's theorems:
Peano and Robinson Arithmetics. Representable functions. Arithmetic of syntax. Incompleteness, and undecidability theorems.

Recursivity :
Turing Machines and variants. The Church-Turing Thesis. Universal Turing Machine. Undecidable problems (the halting and the Post-Correspondance problems). Reducibility. The arithmetical hierarchy. Relations to Turing machines. Turing degrees.

#### Keywords

Gödel, incompleteness theorems, Peano arithmetic, Robinson arithmetic, decidability, recursively enumarable, arithmetical hierarchy, Turing machine, Turing degrees, jump operator, primitive recursive functions, recursive functions, automata, pushdown automata, regular languages, context-free languages, recursive languages, halting problem, universal Turing machine, Church thesis.

#### Learning Prerequisites

##### Recommended courses

Mathematical logic (or equivalent). A good understanding of 1st order logic is required - in particular the relation between syntax and semantics.

##### Important concepts to start the course

1st order logic: syntax, semantics, proof theory, completeness theorem, compactness theorem, Löwenheim-Skolem theorem.

#### Learning Outcomes

By the end of the course, the student must be able to:
• Estimate whether a given theory, function, language is recursive or no
• Decide the class that a language belongs to (regular, context-free, recursive,...)
• Elaborate an automaton
• Design a Turing machine
• Formalize a proof in Peano arithmetic
• Sketch the incompleteness theorems
• Propose a non-standard model
• Argue why Hilbert program failed

#### Teaching methods

Ex cathedra lecture and exercises

#### Assessment methods

Written: 3 hours

Dans le cas de l¿art. 3 al. 5 du Règlement de section, l¿enseignant décide de la forme de l¿examen qu¿il communique aux étudiants concernés.

#### Supervision

 Office hours Yes Assistants Yes Forum Yes

#### Resources

##### Bibliography

Set Theory:

• Thomas Jech: Set theory, Springer 2006
• Kenneth Kunen: Set theory, Springer, 1983
• Jean-Louis Krivine: Theory des ensembles, 2007
• Patrick Dehornoy: Logique et théorie des ensembles; Notes de cours, FIMFA ENS: http://www.math.unicaen.fr/~dehornoy/surveys.html
• Yiannis Moschovakis: Notes on set theory, Springer 2006
• Karel Hrbacek and Thomas Jech: Introduction to Set theory, (3d edition), 1999

Recursion Theory :

• Micheal Sipser: Introduction to the Theory of Computation, Thomson Course Technology Boston, 2006
• Piergiorgio Odifreddi: Classical recursion theory, vol. 1 and 2, Springer, 1999
• Robert I. Soare: Recursively Enumerable Sets and Degres, A Study of Computable Functions and Computably Generated Sets, Springer-Verlag 1987
• Nigel Cutland: Computability, an introduction to recursive function theory, 1980
• Raymond M. Smullyan: recursion theory for methamathematics, Oxford, 1993

Proof theory :

• Wolfram Pohlers: Proof Theory, the first step into impredicativity, Springer, 2008
• A. S. Troelstra, H. Schwichtenberg, and Anne S. Troelstra: Basic proof theory, Cambridge, 2000
• S.R. Buss: Handbook of proof theory, Springer, 1998

Gödel's results :

• Raymond M. Smullyan: Gödel's incompleteness theorems, Oxford, 1992
• Peter Smith: An introduction to Gödel's theorems, Cambridge, 2008
• Torkel Franzen: Inexhaustibility, a non exhaustive treatment, AK Peteres, 2002
• Melvin Fitting: Incompleteness in the land of sets, King's College, 2007
• Torkel Franzen: Gödel's theorem: an incomplete guide to its use and abuse, AK Peters, 2005

### In the programs

• Mathematics - master program, 2019-2020, Master semester 1
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Mathematics - master program, 2019-2020, Master semester 3
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Applied Mathematics, 2019-2020, Master semester 1
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Applied Mathematics, 2019-2020, Master semester 3
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Communication Systems - master program, 2019-2020, Master semester 1
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Communication Systems - master program, 2019-2020, Master semester 3
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Computer Science - Cybersecurity, 2019-2020, Master semester 1
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Computer Science - Cybersecurity, 2019-2020, Master semester 3
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Computer Science, 2019-2020, Master semester 1
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Computer Science, 2019-2020, Master semester 3
• Semester
Fall
• Exam form
Written
• Credits
5
• Subject examined
Gödel and recursivity
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks

### Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Under construction
Lecture
Exercise, TP
Project, other

### legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German