MACHINES DE TURING, FONCTIONS
RECURSIVES et MAPLE
TELECHARGER ! ---- PAGE PRECEDENTE ---- PAGE SUIVANTE ---- RETOUR A LA PAGE PRINCIPALE
02 INTRODUCTION
Au cours du congrès international de mathématiques
de Paris de 1900, Hilbert (1862-1943), alors un des mathématiciens les plus
respectés de son époque, pose 23 questions (dont toutes ne sont pas résolues
aujourd’hui) qu’il estime représenter les principaux axes de recherche en
mathématiques pour les 50 années à venir. Parmi ces questions, celle de la
résolution automatique des équations diophantiennes, qui se généralise au
problème de la démonstration automatique : peut-on construire un système formel
(langage, axiomes, règles de déduction) permettant la démonstration
automatique, donc algorithmique d’un résultat (i.e. par application
systématique des règles de déductions aux axiomes du système et aux hypothèses
de l’énoncé) . Hilbert passa beaucoup de temps, les dernières années de sa vie,
à essayer de construire de tels systèmes.
Pourtant, en 1931, Gödel (1906-1978) résout
le problème, négativement. C’est le fameux théorème d’incomplétude :
" tout système formel arithmétique finiment présentable et w -compatible ne peut être complet ". Bien que les termes
employés aient une définition mathématique précise, que je ne veux évidemment
pas développer ici, la signification intuitive du résultat reste assez facile à
appréhender : une " théorie " mathématique axiomatisée par
un nombre fini d’axiomes ou de " schémas récurrents
d’axiomes ", qui ne contient pas de propositions à la fois
" vraies " et " fausses " (ce qui est
quand même le minimum que l’on puisse exiger !), assez puissante pour englober
l’arithmétique du premier ordre, permet forcément d’énoncer des propositions
qu’on ne pourra pas démontrer " à l’intérieur " de la
théorie. Ce qui tord le cou à l’idée de démonstration automatique ! Il en est
ainsi par exemple, de la théorie des ensembles axiomatisée par Zermelo et Fraenkel
*. Il en est ainsi également, dans une certaine mesure, des systèmes de calcul
formel comme Maple, Mathematica, ... ce qui met en évidence une limitation,
toute théorique, de l’informatique !
* (De même, en 1937, Gödel
lui-même, prouve que l’hypothèse du continu n’est pas démontrable à l’intérieur
de la théorie des ensemble. Cohen prouve en 1962, qu’il en est de même pour la
négation de l’hypothèse du continu)
En 1936, Turing (1912-1954) apporte lui aussi
une réponse négative au 10ème
problème de Hilbert. Turing met au point une théorie mathématique qui n’est
autre que la description logique de ... l’ordinateur. Théorie prémonitoire qui
est, entre autres, à l’origine du développement de l’informatique. Pour cela,
il met en place un " codage de l’information " et de
son traitement (de même que Gödel avait " codé "
l’arithmétique **), qu’on nomme actuellement machines de Turing et qui
lui permet de mettre en évidence les fonctions calculables par ces
machines (les fonctions récursives). Ces fonctions sont en quantité
dénombrable et, l’ensemble des fonctions entières à variables entières
auxquelles il se limite formant un ensemble ayant la puissance du continu,
l’ensemble des fonctions non calculables aussi ! La description des machines
de Turing qu’il donne étant assez vaste pour inclure les ordinateurs les
plus puissants qui soient actuellement (et même plus : mémoire infinie, vitesse
infinie, ... !), le résultat conserve encore de nos jours toute sa
profondeur.
** (Il s’agit de véritable codage et non d’une simple numérotation. Ainsi,
Gödel associe un entier à chaque proposition de l’arithmétique axiomatisée et
inversement, la seule connaissance d’un entier permet, via une étude poussée de
sa décomposition en facteurs premiers, de reconstituer la proposition
arithmétique que contient cet entier. Turing procède de même avec
l’information, comme on va le voir dans ce cours. Turing était en réalité un as
du codage, à tel point qu’il a participé activement pendant la guerre de
1939-1945, au décodage des messages chiffrés allemands - cf. sa bibliographie :
Alan Turing ou l’énigme de l’intelligence, par Andrew Hodges chez Payot)
Les fonctions récursives sont
présentées comme une classe construite à partir de quelques fonctions simples
(les fonctions initiales) et close par un très grand nombre d’opérateurs
fonctionnels de façon à englober apparemment toutes les fonctions usuelles. Il
est en réalité assez difficile de construire explicitement une fonction non
récursive (Tibor Rado y parvient en 1962 avec la fonction dite de la fourmi
laborieuse. L’idée est que cette fonction est non calculable parce qu’elle
croît beaucoup trop fortement !).
La construction de la classe des fonctions
récursives est totalement algébrique et c’est donc aussi, en plus de sa
dénombrabilité, un des points surprenants du résultat établi par Turing (théorème
de caractérisation) assurant la coïncidence de cette classe avec celle des
fonctions calculables par un ordinateur i.e. une machine de Turing (les fonctions
Turing-calculables). Historiquement, l’idée d’itérer des définitions
récursives à partir de quelques fonctions ou énoncés simples a été introduite
par Hilbert (" Sur l’infini " en 1920) puis par Gödel
(" Sur les propositions formellement indécidables " en
1931). La présentation retenue dans ce cours résulte des travaux de Kleene, un
élève de Church.
Enfin, la coïncidence entre la classe des fonctions
récursives et celle des fonctions Turing-calculables est tellement
remarquable qu’elle est à l’origine de ce qu’on appelle maintenant la thèse
de Church : les fonctions récursives coïncident avec les fonctions définissables
par algorithme.
On trouvera donc pour l’instant, dans la présente
livraison, le cours et des exercices corrigés, sous forme papier et fichiers
Word .
On trouvera également, sous forme papier et
fichiers Maple, les procédures et exemples en Maple, illustrant l’intégralité
des notions développées dans le cours et les exercices correspondants. Les
techniques de programmation utilisées (variables, fonctions, procédures,
algorithmes, astuces informatiques, idiotismes Maple et combines diverses) sont
explicitées en détail dans ces fichiers :
1. Cours polycopié PolyMapleTuring.doc
2. Machines de Turing matrices.mws
3. Turing-calculabilité et récursivité calcrecu.mws
4. Initialisations turexe.mws
Tous ces fichiers sont regroupés dans le
fichier téléchargeable turing.zip
à déziper.
Suivront plus tard, une table des matières
détaillée, un glossaire, une preuve plus explicite du théorème de
caractérisation, ... , toutes choses dont l’absence n’empêche pas de
profiter des simulations en Maple. Ce qui est un peu le but de ce travail.
Quelques
remarques d’ordre technique pour terminer.
Il est préférable d’exécuter les programmes
Maple sur une machine relativement puissante, les boucles imbriquées et tests
enchaînés étant assez nombreux dans les procédures. En réalité, ces simulations
Maple sont un jeu, permettant certes de s’exercer à la programmation Maple,
mais un jeu néanmoins puisqu’il s’agit au fond, de simuler le fonctionnement
d’un ordinateur (les machines de Turing) sur ... un ordinateur !
Ainsi, plutôt que d’exécuter entièrement les
deux fichiers matrices.mws et calcrecu.mws comportant de nombreux exemples et commentaires, ce
qui risque de saturer la mémoire, il est plus judicieux d’exécuter d’abord le
fichier turexe.mws, qui charge toutes les variables, fonctions et
procédures utiles et ensuite, de consulter dans les deux autres fichiers les
sources des définitions et procédures et de valider les exemples. Si la mémoire
vient quand même à manquer, on la libère avec un restart (ou on
relance Maple, ce qui est plus efficace) et on recommence l’opération.
DEBUT DE PAGE ---- PAGE PRECEDENTE ----PAGE SUIVANTE ---- RETOUR A LA PAGE PRINCIPALE