MACHINES DE TURING, FONCTIONS RECURSIVES et MAPLE

On trouvera ici un cours et des programmes de simulation en Maple
sur les machines de Turing et les fonctions récursives.

TELECHARGER ! ----- PAGE SUIVANTE ----- RETOUR A LA PAGE PRINCIPALE

01 PREAMBULE

J’avais créé, en 1988 à l’E.N.T.P.E., un cours optionnel de mathématiques, intitulé assez rébarbativement je l’avoue, " Algorithmique théorique et Calculabilité effective " (publié sous le même titre, chez Eyrolles, en 1989) .

Ce cours traitait dans un premier temps, des fondements logiques de l’informatique, par l’intermédiaire des machines de Turing et des fonctions récursives (incluant une approche des fonctions universelles et du problème de l’arrêt). Il abordait dans une deuxième partie, la thèse de Church et les problèmes de complexité des algorithmes (problèmes NP-complets, théorème de Cook et NP ¹ P).

Bien qu’assez abstrait, ce cours fut bien reçu par les étudiants qui y virent une approche différente de l’informatique, loin des connotations de rendement, de technologie et d’utilitarisme qu’elle draine parfois. C’était mon but.

De mon côté, je me rappelle que pour " vendre " cette option, c’est à dire, pour attirer le plus grand nombre possible d’étudiants à ce cours optionnel (!), j’avais recours à la métaphore suivante. Je comparai l’informatique à la conduite automobile. On peut ainsi " se servir d’un ordinateur " (traitement de texte, tableur, ...) sans rien connaître de son fonctionnement, de même qu’on peut conduire une voiture sans aucune notion de mécanique; c’est le niveau zéro. (Rien de péjoratif à cette appellation car c’est en fait la destination des ordinateurs et des automobiles que de pouvoir être utilisés facilement et sans formation préalable longue). Un niveau un peu supérieur consiste, en ce qui concerne l’automobile, à savoir changer une roue, mettre de l’huile dans le moteur, changer des plaquettes de freins éventuellement, c’est à dire, en informatique, sauver un fichier, créer des dossiers et des raccourcis sous Windows ou écrire un petit programme .bat sous DOS. Le niveau qui semble être le sommet est alors celui de la programmation et du développement de logiciels d’un côté et de la réparation complète d’un moteur ou d’une carrosserie de l’autre. Mais il est néanmoins un niveau de perception différent de l’automobile comme de l’informatique, qui se traduit pour l’automobile, par la connaissance des notions de thermodynamique, de mécanique et de mécanique des fluides entre autres, permettant la compréhension théorique du moteur à explosion, de la solidité d’un châssis ou de l’aérodynamisme d’une carrosserie. C’est à ce niveau là que ce situait, en informatique, le cours que je développai. (On peut remarquer d’ailleurs que tous ces niveaux de compréhension ne s’impliquent pas les uns les autres, ce qui conduit parfois à des situations risibles. Il existe ainsi sans aucun doute, des thermodynamiciens éminents incapables de remplacer une bougie dans un moteur ou, par exemple, à l’inverse et dans l’autre domaine considéré, des programmeurs experts n’ayant aucune idée de ce que peut représenter le théorème de Gödel).

Cette parenthèse fermée, je reviens à l’historique de mon cours.

En 1995, sous diverses pressions mal identifiées, je fus obligé de suspendre cet enseignement jugé avant tout trop théorique. Le calcul formel faisant son apparition dans les classes préparatoires (avec Maple surtout et Mathématica un peu), on me demanda de mettre au point un nouveau cours optionnel de mathématiques, dont l’intitulé pourrait être " Calcul formel : Maple " mais dont le contenu n’était pas précisément délimité pourvu que l’outil Maple fût employé. Ce qui fut fait.

J’assure donc actuellement à l’E.N.T.P.E., parmi d’autres enseignements, un cours de mathématiques optionnel effectivement intitulé " Calcul formel : Maple ".

Pratiquement, deux objectifs sont visés. D’abord une maîtrise avancée de l’outil Maple, tant au niveau de la connaissance précise des si nombreuses primitives du langage, de sa structure et de sa syntaxe, qu’au niveau de l’exploitation du logiciel, avec par exemple, la création de packages, l’exploitation de routines en langage C ou l’interconnexion avec un logiciel de Calcul comme Mathlab. Ensuite et c’est la partie libre du cahier des charges, je développe avec Maple, l’étude d’algorithmes complexes, la résolution de problèmes de mathématiques de tous ordres et ... les fondements théoriques de l’informatique avec l’étude des machines de Turing et des fonctions récursives. Il va de soi que les deux objectifs se complètent.

J’ai donc entre autres, en reprenant le formalisme de mon cours de 1988, réalisé une simulation complète et avancée avec Maple, des machines de Turing et des fonctions récursives. Les machines de Turing " fonctionnent " en temps réel (on visualise par des animations, le déplacement de la tête sur le ruban, avec gestion de la mémoire) et peuvent être assemblées en systèmes complexes. On peut alors constater comment les fonctions récursives sont Turing-calculables et réciproquement (ce qui est un des grands résultats de la théorie).

Maple étant maintenant passé dans les moeurs des classes préparatoires et les programmes d’informatique de certaines d’entre elles incluant des notions d’informatique assez théoriques (automates et langages, arbres, ...), j’ai pensé que la mise à disposition du formalisme des machines de Turing et des fonctions récursives (définitions, théorèmes et démonstrations) ainsi que les fichiers Maple réalisant les simulations correspondantes intéresseraient certains. Il s’agit là finalement, d’un bon entrainement à la programmation Maple, joint à l’étude de concepts de base non triviaux de l’informatique.

Le cours est composé pour l’instant de fichiers au format Word et sera bientôt sous TEX.

Les programmes Maple sont exploitables par tous, pourvu que leur origine soit citée, mais peuvent surtout être modifiés et optimisés. Que les auteurs d’améliorations d’une quelconque procédure ou de prolongements divers n’hésitent pas à me contacter et me pardonnent mes maladresses et mes erreurs.

Amusez-vous bien !

TELECHARGER ! ----- DEBUT DE PAGE ----- PAGE SUIVANTE ----- RETOUR A LA PAGE PRINCIPALE