Théorie des automates
Un article de Wikipédia, l'encyclopédie libre.
La théorie des automates, intimement liée à l'étude des langages formels, est une branche de l'informatique théorique qui étudie la puissance de calcul de divers modèles d'automates finis.
[modifier] Vulgarisation
Un automate est une machine prenant en entrée des propositions quelconques comme, par exemple, « (1 + 3) / ( 5 - 1) = 1 » et retournant vrai ou faux, en fonction de ce que l’on attend de la machine ; une évaluation syntaxique ou sémantique. Dans le cas d’une évaluation syntaxique, on désire que la machine évalue si la proposition est correctement formée ou non. Par exemple, « (1 + 3) / ( 5 - 1) = 2 » est correctement formée alors que « ++1 + 3) / )5 - 1) = 2 » ne l’est pas. Dans le cas d’une évaluation sémantique, on désire que la machine évalue la valeur de vérité de la proposition, par exemple : « (1 + 3) / ( 5 - 1) = 2 » est fausse alors que « (1 + 3) / ( 5 - 1) = 1 » est vraie.
L’étude des automates concerne donc l’étude de la syntaxe des langages formels et des langues naturelles ainsi que de la calculabilité, soit l’étude des limites de calcul qu’une machine particulière peut réaliser. L’étude de la syntaxe et celle de la sémantique sont équivalentes ; les limites de reconnaissance syntaxique d’un automate sont équivalentes à sa puissance de calcul et vice-versa. En effet, que l’on utilise un automate pour réaliser de la syntaxe ou de la sémantique est inconnu de la machine, cette distinction est purement artificielle.
En 1937, Alan Mathison Turing démontra qu’une sorte particulière d’automate, la machine de Turing, pouvait calculer ce que tout autre automate pouvait calculer et qu’il était impossible de faire mieux. Cette machine était aussi puissante, au niveau du calcul, que tout mathématicien. Il démontra également qu’il existe une sorte particulière de machine de Turing, la machine de Turing universelle, qui peut reproduire le comportement de n’importe quelle autre machine de Turing ; l’ordinateur était né.
Contrairement à ce que l'on pourrait croire, la machine de Turing n'est pas l'achèvement de la théorie des automates mais bien le commencement. La théorie des automates fut développée pour comprendre comment émergeait la prodigieuse capacité de calcul des machines de Turing. Il fallut attendre 1956 pour que le premier théorème autre que ceux de Turing apparaisse, il s'agit du théorème de Kleene, démontrant l'équivalence entre les graphes de transition, les automates finis et les grammaires régulières. Le théorème de Kleene réalisa pour la première fois l'adéquation d'un automate, considéré comme un accepteur de langage, et d'une grammaire formelle considérée comme un générateur de langage.
Stephen Cole Kleene a étudié une version simplifiée de la machine de Turing pour mieux la comprendre, il a dépouillé la machine de Turing de sa mémoire (son ruban) et trouvé un moyen de décrire ce que fait cette machine simplifiée, soit quel langage elle génère. La méthode de Kleene fut par la suite la principale méthode employée pour l'avancement de la recherche.
Au cours des années suivantes, les chercheurs débordèrent d'imagination pour créer différentes variations de la machine de Turing; machine à une pile, à deux piles et plus, machine à queues, machine de post, machines à registres, etc. Ils s'aperçurent rapidement que malgré leurs efforts, la variation n'était qu'une illusion et que tout automate s'inscrivait dans une des quatre catégories qu'ils avaient découverte. La puissance de calcul des automates pouvait être organisée en une hiérarchie à quatre niveaux, les automates d'une hiérarchie supérieure pouvant calculer tout ce que peut calculer un automate de niveau inférieur.
Ce fait avait pourtant déjà été mentionné par le linguiste Noam Chomsky qui étudiait les grammaires formelles, il avait découvert en 1956 qu'il existait seulement quatre types de grammaires, les grammaires supérieures comprenant l'expressivité des grammaires inférieures. La stricte équivalence de ces quatre grammaires avec les quatre types d'automates fait de Noam Chomsky un des pères fondateurs de l'informatique théorique.
[modifier] La naissance d'une nouvelle science
La machine de Turing n'est pas simplement une abstraction originale, elle est la réponse à une question philosophique fondamentale : la mathématique est-elle un artefact de l'esprit humain ou fait-elle corps avec la nature? Autrement dit, l'harmonie des sphères n'est-elle qu'une illusion produite par l'appareil cognitif de l'humain ou bien les lois de la nature sont bel et bien écrites en langage mathématique?
Kant fut extrêmement ébranlé par l'adéquation des équations de la physique de Newton à la réalité phénoménologique. En effet, comment la mathématique, pure expression des connaissances a priori de l'entendement, peut-elle réaliser une quelconque adéquation avec une réalité dont elle ignore tout? Si la nature réelle de la mathématique est une question philosophique d'importance depuis l'antiquité, le succès de la physique remit au goût du jour cette vieille question.
La thèse de Church-Turing qui postule qu'aucune machine ne peut faire mieux qu'une machine de Turing (réaliser un calcul qu'une machine de Turing ne pourrait effectuer) est une réponse finale à la question de la nature de la mathématique. En effet, ce postulat implique directement que si aucune machine ne peut faire mieux, alors aucun phénomène naturel non plus car sinon il serait possible de construire une machine impossible en utilisant ce phénomène naturel. Par conséquent, tout phénomène naturel est calculable (ne pas confondre avec modélisable) et l'adéquation d'un modèle calculable avec un phénomène calculable n'est certainement pas surprenant.
L'étude des automates est donc, en fait, l'étude de la structure fine de l'univers et est, en ce sens, une science naturelle. Le terme automate laisse malheureusement penser que cette nouvelle science ne concerne que les artefacts sophistiqués que sont les ordinateurs. Pourtant, la définition même de l'automate fini déterministe qui est l'automate le plus simple, est un système composé d'états distinguables les uns des autres et dont le changement d'état nécessite un événement (une cause). Cette définition englobe tout phénomène naturel connaissable, c'est-à-dire, sur lequel il est possible de développer des connaissances. L'utilisation de ce type d'automate en science naturelle et humaine est maintenant largement répandue. Nous devons à Norbert Wiener la diffusion de l'utilisation d'automates pour la formalisation des connaissances (cybernétique).
