Ensemble des résultats mathématiques concernant les modèles utilisés et les questions posées d’une part par l’étude de l’intelligence artificielle et de la cybernétique, d’autre part par la synthèse des automatismes et des calculateurs numériques.

Le quintuple

Le modèle de base est l’automate A, usuellement symbolisé par une boîte avec des entrées X et des sorties Y, formalisant la notion de mécanisme doué de mémoire.

En l’absence de mémoire, le signal de sortie émis par une telle boîte, en réponse à des signaux d’entrée X, ne dépend que du dernier signal reçu, et le fonctionnement est statique ; si le nombre de signaux d’entrée est fini, la boîte représente une machine à logique combinatoire. En revanche, le fonctionnement est dynamique et la machine a une logique séquentielle si les signaux de sortie dépendent de l’histoire passée des signaux d’entrée. L’automate fini A mémorise dans sa structure interne Q, appelée espace d’état, un nombre fini de renseignements sur les signaux reçus antérieurement, et il produit des sorties en fonction à la fois de son état et du dernier signal d’entrée. La séparation de la mémoire et de la logique combinatoire C d’un automate suggère une forme canonique de sa structure interne.

La logique C de l’automate A peut être spécifiée sur une table de transition (ou table de fluence) ayant une ligne par symbole d’entrée x et une colonne par état q, qui spécifient à leur intersection le nouvel état que mémorisera la machine et le symbole de sortie qu’elle émettra si elle reçoit le symbole x alors qu’elle est en l’état q. Une représentation graphique consiste à définir un nœud d’un graphe pour chaque état de l’automate et une flèche allant du nœud d’un état à celui de l’état suivant pour tout symbole d’entrée induisant le changement correspondant en mémoire.

Les signaux d’entrée, en nombre fini, sont considérés comme les symboles d’un alphabet X. L’ensemble des mots, qui sont des séquences de longueur finie de symboles, est l’itéré X* de X.

Un automate fini est un quintuple possédant trois espaces et deux fonctions : A = (X, Q, Y, τ, σ) ; l’espace d’action X, ou alphabet d’entrée, comprend un nombre fini de commandes externes (boutons ou interrupteurs pour un automatisme, micro-instructions pour un calculateur numérique) ; l’espace d’état Q est l’ensemble fini des situations internes possibles (positions de relais mécaniques, situations de bascules électroniques) affectant les réactions de l’automate ; l’alphabet de sortie Y fini représente les situations observables de l’extérieur ou le résultat du travail de l’automate (déclenchement d’un signal d’alerte, réponse à un test logique). La fonction de transition τ spécifie, pour chaque état q de Q, l’état q′ = τ(q, x) atteint sous l’action x de X ; et la fonction de sortie σ indique la valeur y = σ(q, x) de Y correspondant à toute situation où peut se trouver l’automate. L’écoulement du temps et la cadence du fonctionnement sont donc induits par le rythme des signaux d’entrée.

Ce point de vue interne permet de distinguer entre machines séquentielles asynchrones et synchrones, et entre diverses propriétés de l’espace d’état (minimalité, atteignabilité, observabilité).

La boîte noire

Ces considérations structurelles amènent à développer une approche behavioriste si l’on désire utiliser l’automate en modèle a priori de phénomènes naturels (physiques, psychologiques, etc.). Ce point de vue expérimental impose l’hypothèse d’un état initial q₀ spécifié, et la possibilité soit de ramener à volonté l’automate en q₀, soit de disposer de plusieurs copies de « boîtes noires » A identiques au départ. Le comportement de l’automate initialisé (A, q₀) est décrit par la liste des signaux de sortie σ[τ(q₀, m)] résultant de l’application de tout mot d’entrée m. Chaque relation entrée-sortie est appelée une expérience, et leur liste définit la fonction séquentielle de l’automate initialisé.