Décidabilité
Cette page contient les résumés du cours de décidabilité et les
énoncés
de td. Ils sont
disponibles en trois formats.
Chapitre 1 : Introduction à la
décidabilité:ps,
ps.gz,
pdf.
Chapitre 2 : Machines de Turing: ps,
ps.gz,
pdf.
Chapitre 3 : Fonctions récursives: ps,
ps.gz,
pdf.
Chapitre 4 : Récursivité: ps,
ps.gz,
pdf.
Chapitre 5 : Connaissance des ensembles
d'entiers: ps,
ps.gz,
pdf.
Chapitre 6 : Indécidabilité du problème
du mot: ps,
ps.gz,
pdf.
Chapitre 7 : Indécidabilité du calcul des
prédicats:
ps,
ps.gz,
pdf.
Chapitre 8 : Indécidabilité de l'arithmétique
de Péano: ps,
ps.gz,
pdf.
.
Les énoncés sont disponibles (merci de m'avoir passé les sources !)
TD 01 : Codage sur N:
ps,
en ps.gz,
et en pdf.
TD 02 : Machines de Turing:
ps,
en ps.gz,
et en pdf.
TD 03 : Fonctions récursives primitives I:
ps,
en ps.gz,
et en pdf.
TD 04 : Fonctions récursives primitives II:
ps,
en ps.gz,
et en pdf.
TD 05 : Fonctions calculables et castor affairé:
ps,
en ps.gz,
et en pdf.
TD 06 : Systèmes de programmation:
ps,
en ps.gz,
et en pdf.
TD 07 et 08 : Théorème de Rice généralisé (2 séances):
ps,
en ps.gz,
et en pdf.
TD 09 : Ensembles d'entiers:
ps,
en ps.gz,
et en pdf.
TD 10 : Logique mathématique:
ps,
en ps.gz,
et en pdf.