Gödel et récursivité

Français | English

Ce cours a été donné au printemps 2011.

Il sera à nouveau donné au printemps 2013.

Modalités

Professeur : Jacques DUPARC (Jacques.Duparc[at]unil.ch)
Assistant : Yann Pequignot (Yann.Pequignot[at]unil.ch)

Cours : Lundi, 8:15 - 10:00 salle CE1104
Exercices : Mercredi, 12:15 - 14:00, salle MAA112

Objectifs

Ce cours vise tout d'abord à exposer les théorèmes d'incomplétudes et d'indécidabilité de Gödel, puis les liens entre la théorie des fonctions récursives, l'informatique et la hiérarchie arithmétique.

Contenu

Théorème de Gödel:

Arithmétique de Peano et de Robinson. Fonctions représentables. Arithmétisation de la syntaxe. Théorèmes d’incomplétude et d’indécidabilité.

Récursivité:

Machines de Turing et variantes. La thèse de Church-Turing. Machine de Turing universelle. Problèmes indécidables (le problème de la halte et la correspondance de Post). Reducibilité. La hiérarchie arithmétique. Relations aux machines de Turing. Degrés de Turing.

Examen

Documents distribués en cours ou en séries (en format pdf)

Bibliographie

Théorie des ensembles :

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

Théorie de la récursion :

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

Théorie de la démonstration :

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

Résultats de Gödel :

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

Contacts

Jacques.Duparc[at]unil.ch
Yann.Pequignot[at]unil.ch

Rechercher:

Annuaires Site map

Name
Password

isAnon => cache