Théorie des automates - Définition

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 (jugements synthétiques a priori), 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).