MATH-483 / 5 credits

Teacher: Duparc Jacques

Language: English

Remark: Cours donné en alternance tous les deux ans

## Summary

Gödel incompleteness theorems and mathematical foundations of computer science

## Content

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.

Gödel's theorems:
Peano and Robinson Arithmetics. Representable functions. Incompleteness, and undecidability theorems in arithmetics.

If time permits, the completeness of the first order theory of the field of real numbers.

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

## 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

No

## 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

• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Gödel and recursivity
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional

## Reference week

Thursday, 13h - 15h: Lecture MAA331

Thursday, 15h - 17h: Exercise, TP MAA331

## Related courses

Results from graphsearch.epfl.ch.