Historique

Autrefois, un procédé de calcul faisait l'objet d'un discours mathématique en langage clair. L'Algorithme d'Euclide était décrit ainsi par un énoncé discursif.

La notation symbolique des nombres a été développée au VII^ème siècle par un grand astronome indien : Brahmagupta. Abbou Adullah Ibn Moussa dit Al Khorizmi, né en 783, mathématicien ouzbeck de l'Empire des Samanides donna la solution de l'équation du second degré et définit les règles de transformation des expressions (algèbre) à partir des travaux de Brahmagupta. Il écrivit une encyclopédie des procédés de calcul qui sera diffusée dans le monde entier, traduite en latin. On appellera « algorithme » un procédé de calcul figurant dans cet ouvrage, le nom de l'auteur se trouvant en tête. Puis on dénommera algorithme tout procédé de calcul voire même tout raisonnement formel.

Jusqu'au XX^ème siècle il était admis que la solution de tout problème pouvait faire l'objet d'un algorithme et de manière plus générale qu'il existait un algorithme universel permettant de résoudre tout problème, choisissant automatiquement la méthode adaptée à sa solution.

La recherche de cet algorithme universel était un des grands problèmes de la mathématique. Il a été clairement énoncé pour la première fois par Leibnitz.
En 1901, il faisait partie de la série des problèmes ouverts proposés par Hilbert à la sagacité universelle.
L'algorithme est une classe particulière d'opérations intelligentes bien définie mathématiquement. Nous allons en donner la définition exacte :

Algorithme

Suite de prescriptions précises qui dit d'exécuter dans un certain ordre des opérations réalisables pour aboutir au bout d'un nombre fini d'opérations à la solution de tous les problèmes d'un certain type donné.

Commentaire :

Un algorithme contient tout ce qui permet de l'exécuter, il est non-ambigu et indépendant du contexte (context-free en anglais). C'est sa définissabilité.

Un algorithme définit une classe de problèmes. Il est capable de résoudre tous les problè-mes de cette classe. Exemple : l'algorithme de l'addition donne un résultat correct quels que soient les opérandes. On parle de la massiveté d'un algorithme. Il y a isomorphisme entre un algorithme et la classe de problèmes qu'il résout.

Un algorithme doit donner son résultat au bout d'un nombre fini d'opérations, même si ce nombre est très grand et si l'algorithme n'est pas physiquement réalisable. Par exemple l'algorithme combinatoire qui résout le jeu d'échecs est fini au sens mathématique, alors que sa taille interdit de le réaliser physiquement. Il faudrait une mémoire de la taille de l'Univers connaissable ! C'est le problème du « mur du combinatoire ». Un algorithme potentiellement réalisable peut n'être pas physiquement réalisable.

L'histoire de l'« algorithme universel », Alan TURING et sa machine.

Ainsi donc comme nous l'avons mentionné, durant plusieurs siècles et jusqu'à une période récente, on supposait l'existence d'un algorithme universel, c'est à dire l'existence d'un procédé de calcul permettant de résoudre sans réfléchir tout problème donné. De plus il était implicitement admis que toute opération intelligente pouvait être décrite par un algorithme.
Formulé de manière explicite par Leibniz, ce problème fut re-posé par HILBERT en 1901, puis ramené au problème dit de la « décision de la décidabilité » également par HILBERT en 1928.
En 1935, un jeune mathématicien anglais, Alan TURING imagina une machine idéale pour exécuter tout algorithme et la décrivit dans une publication célèbre en 1937.
Cette machine était constituée :

• -- d'une bande de papier infinie composée d'une suite de cases pouvant contenir un seul symbole ou être vide.
• -- d'une unité de contrôle située devant une case et qui pouvait :
  
  • - lire, écrire, effacer ce qu'il y avait dans la case située devant elle,
    
  • - se déplacer d'une case à droite ou à gauche.

À un instant donné, cette unité de contrôle est dans un certain état.
L'étape suivante ou le changement d'état est dicté par :

• - ce qu'il y a dans la case,
  
• - l'état présent de l'unité.

Les règles qui fixent l'action sont mises sous forme d'une table des états dans l'unité de contrôle qui alors opère toute seule. TURING montra qu'il existe une table des états pour tout algorithme, et donc qu'il existe une machine de ce type (maintenant appelée « machine de Turing ») pour tout algorithme. Dans le cas d'une machine de Turing binaire, il y a dans chaque case 0, 1 ou rien.

La machine de Turing est un automate algorithmique universel, et TURING pensait avoir décrit la machine intelligente universelle.
Mais en 1931, un mathématicien autrichien, Kurt GÖDEL, avait démontré un théorème célèbre dont une des principales conséquences était que certains problèmes que l'intelligence humaine savait résoudre ne pouvaient pas être résolus par un algorithme ! Et un autre mathématicien, Alonzo CHURCH, montra en 1936 que cela conduisait à l'impos-sibilité du fameux problème de la décision de la déductibilité, base de l'algorithme universel, et par conséquent à l'impossibilité de réaliser l'algorithme universel.
La vérité scientifique oblige à dire qu'on n'en tira toutes les conséquences que vingt ans après (NOVIKOV, 1955, travaillant sur les chaïnes de MARKOV) en s'interrogeant sur des difficultés rencontrées dans l'usage des ordinateurs pour résoudre certains types de problèmes. Nous verrons l'importance de cette question dans les recherches actuelles sur l'intelligence artificielle.

Les chaînes de MARKOV, formalisation des algorithmes

Un autre objet mathématique a aussi joué un rôle important dans la théorie des algorithmes : la chaîne de MARKOV (décrite en 1914 par un mathématicien norvégien, THUE, et dont les propriétés ont été étudiées par le mathématicien russe Andréi A. MARKOV). Il s'agit d'une suite de caractères alignés. Et on se pose le problème de la règle systématique qui, appliquée à cette chaîne, puis encore au résultat, permet d'arriver à une autre chaîne donnée. Ce problème qui semblerait relever des mathématiques amusantes a pris un grand intérêt lorsqu'on a montré qu'il y avait un isomorphisme entre les algorithmes et les chaînes de MARKOV. On disposait donc d'une formalisation mathématique de l'algorithme et les théorèmes sur les transformations des chaînes de MARKOV pouvaient s'appliquer aux algorithmes. Nous avons là un exemple intéressant du rôle que peuvent jouer du jour au lendemain des travaux mathématiques apparemment de la plus totale gratuité.

Bibliographie

BRETON Philippe - Histoire de l'informatique - Paris, La Découverte, 1987.
FONT Jean-Marc, QUINIOU Jean-Claude, VERROUST Gérard - Les Cerveaux non-humains, Introduction à l'informatique - Paris, Denoël, 1970.
IFRAH Georges - Histoire Universelle des Chiffres - Paris, Laffont (Bouquins), 1994.
PERRIAULT Jacques - Éléments pour un dialogue avec l'informaticien - Paris, EPHE/Mouton, 1971.
TRAHTENBROT B.A.- Algorithmes et machines à calculer - Paris, Dunod, 1963.