Vous êtes ici: UNIL > HEC > LOGIQUE > Enseignement > Gödel et récursivité (EPFL)
Français | English

Gödel et récursivité (EPFL)

General information

Professor : Jacques DUPARC (Jacques.Duparc[at]unil.ch)
Assistants : Yann Pequignot (Yann.Pequignot[at]unil.ch)
                  Kevin Fournier (Kevin.Fournier[at]uni.ch)

Lecture : Lundi, 8:15 - 10:00 salle MAA330
Exercises : Mercredi, 12:15 - 14:00, salle MAA330

Documents

Sheet
Solution
Sheet1
Solution1
Sheet2 Solution2
Sheet3
Solution3
Sheet4(updated 14.03)
Solution4
Sheet5
Solution5
Sheet6 Solution6
Sheet7
Solution7
Sheet8
Solution8
Sheet9 Solution9    
Sheet10
Solution10 (Sol de l'exo 2 en français, ici)
Sheet11
Solution11
Sheet12
Solution12
# #
 
Lecture notes from Logique Mathématique I (in french) : pdf

The Philosophical Significance of Tennenbaum’s Theorem, by Tim Button and Peter Smith


Goals

This course presents Gödel’s incompleteness, and undecidability theorems which showed that Hilbert’s program could not be carried out. Then it visits the relations between recursion theory, theoretical computer science and the arithmetical hierarchy. Contents 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.

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
Rechercher:
 
 
Internef - CH-1015 Lausanne - Suisse - Tél. +41 21 692 33 00 - Fax +41 21 692 33 05