Le but de cette introduction à la calculabilité (
.ps.gz
)(
.dvi.gz
) est de définir les problèmes
dont les solutions sont calculables par un algorithme.
Un problème est assimilé au langage de ses instances positives.
Nous décrivons donc d'abord la classe des langages réguliers (
.ps.gz
)(
.dvi.gz
) décrits par les expressions régulières
et nous établissons le parallèle avec une
modélisation des ordinateurs et des programmes (
.ps.gz
)(
.dvi.gz
)
par les automates finis (
.ps.gz
)(
.dvi.gz
)
et un type particulier de grammaires
(
.ps.gz
)(
.dvi.gz
), les grammaires régulières.
En fait les expressions régulières (en description), les automates finis (en analyse) et les grammaires régulières
(en génération) caractérisent les langages
réguliers (
.ps.gz
)(
.dvi.gz
). Le théorème du gonflement pour les langages réguliers (
.ps.gz
)(
.dvi.gz
) montre leurs limites dues à l'hypothèse selon laquelle la
mémoire (le nombre d'états) est finie.
Nous introduisons donc les automates à piles (
.ps.gz
)(
.dvi.gz
) qui ajoutent une pile aux automates finis indéterministes pour
atteindre une mémoire infinie.
Les automates à pile sont équivalents aux grammaires
hors-contexte (
.ps.gz
)(
.dvi.gz
) qui génèrent les langages hors-contexte (
.ps.gz
)(
.dvi.gz
). Encore une fois, le théorème du gonflement pour les automates
à pile (
.ps.gz
)(
.dvi.gz
) montre les limites dues à la structure en pile de la
mémoire. Nous introduisons donc les machines de Turing (
.ps.gz
)(
.dvi.gz
) qui disposent d'une mémoire non bornée sans discipline
d'accès. Nous introduisons alors les notions de langage récursif
(ou décidé par une machine de Turing) et de langage
récursivement énumérable (ou acceptré par une
machine de Turing) et nous donnons des résultats de
décidabilité pour les automates (
.ps.gz
)(
.dvi.gz
). Aucune extension aux machines de Turing n'augmentant l'espace des langages
décidables, nous en venons à émettre la Thèse de
Turing-Church (
.ps.gz
)(
.dvi.gz
) selon laquelle les langages reconnus par un algorithme sont exactement ceux
décidés par une machine de Turing (y allant de même pour les
fonctions calculables par une machine de Turing (
.ps.gz
)(
.dvi.gz
)).
Cette thèse est confortée par une autre approche à la
calculabilité due à Church qui étudie les fonctions
définies sur les naturels, les fonctions récursives (
.ps.gz
)
(
.dvi.gz
). Nous nous tournons alors vers une succinte analyse des langages non
décidables (
.ps.gz
)(
.dvi.gz
) (problèmes de l'arrêt) et des techniques pour démontrer
l'indécidabilité (diagonalisation et méthode de
réduction).
Nous concluons par un résumé des résultats principaux (
.ps.gz
)(
.dvi.gz
) observés sur les automates, les grammaires et la décidabilité.
TD sur les automates finis et à pile (
.ps.gz
)(
.dvi.gz
)
TD sur les machines de Turing (
.ps.gz
)(
.dvi.gz
)
TD sur les fonctions récursives: écriture sans lambda (
.ps.gz
)(
.dvi.gz
)
TD sur les fonctions récursives: écriture avec lambda (
.ps.gz
)(
.dvi.gz
)
"Introduction à
la calculabilité", Pierre Wolper, InterEditions, Collection
iia, 1991, 268 pages (ISBN 2 7296 0372 7).
"Calculabilité
effective et Algorithmique théorique", Patrick Vollat, Eyrolles,
1989, 186 pages.
"Fondements mathématiques
de l'informatique", Jacques Stern, Ediscience internationale, 1990,
318 pages (ISBN 2 84074 065 6).
"Introduction to automata
theory, languages, and computation", John E. Hopcroft and Jeffrey
D. Ullman, Addison-Wesley, 1979, 418 pages (ISBN 0 201 02988).
"Introduction to algorithms", Thomas H. Cormen, Charles E. Leisersnon and Ronald L. Rivest, MIT Press, McGraw-Hill, 1990, 1028 pages (ISBN 0 262 03141 8 (McGraw-Hill), ISBN 0 07 013143 0 (MIT Press)).
 |
"Gödel, Escher, Bach : les brins d'une guirlande éternelle", Douglas Hofstadter, Inter-éditions, 1993. |