You are here :


Indécidabilité et Incomplétude

Master 1ère année de Mathématiques-Informatique




COURS : LE LUNDI : 8h00 - 10h00, SG Salle 1020

Travaux Dirigés : LE VENDREDI / 12h30 - 14h30 / 1/2 LE MERCREDI 8h00 - 10h00 SG Salle 1015
L'OBJECTIF

Comprendre la portée des résultats d’indécidabilité et d’incomplétude. Maitriser les méthodes élémentaires de preuve de décidabilité.
PLAN DU COURS

.Rappel sur les fonctions récursives. Thèse de Church.
.Ensembles récursifs et ensembles récursivement énumérables.
.Problèmes décidables. Problèmes indécidables.
.Prouvabilité dans l’arithmétique de Peano. Fonctions représentables.
.Indécidabilité de l’arithmétique de Peano. 1er théorème d’incomplétude de Goedel.
.Méthode d’élimination des quantificateurs. Exemples de théories décidables (arithmétique de Presburger,...).
BIBLIOGRAPHIE

. Logique Mathématique, cours et exercices, tome 2,, R. Cori et D. Lascar [ Dunod 2003 ]
. Les théorème de limitation, P. Dehornoy [ .pdf ]

[ Top ]

Site Saerch Web Search

Search Tips| Sitemap | FreeFind
List all links on this page
What's New?


 



Pour lire le ficher [ PostScript ] télécharger : GSView

GSView