La Saga des algorithmes

 14 mai 2022
 Yvan Lavallée

Pour un exposé sur les concepts de base:

https://www.youtube.com/watch?v=Xn0wuan_7-0

S’il est vrai que les algorithmes sont utilisés depuis au moins 300 ans avant notre ère (algorithme d’Euclide, Thésée et le minotaure, algorithme du labyrinthe –fil d’Ariane-…) et qu’ils doivent de s’appeler ainsi du nom du mathématicien perse (de Tachkent) Muhammad Ibn Mūsā al-Khuwārizmī (VIIe siècle de l’Hégire) qui décrivit étape par étape, de façon algorithmique la résolution de l’équation du second degré, ils doivent toutefois leur modernité depuis le 28 mai 1936 à un jeune mathématicien de 24 ans, quasi inconnu ; Alan Mathison Turing qui propose une « expérience de pensée », la Machine de Turing Universelle pour démontrer un théorème d’indécidabilité avec lequel un autre mathématicien, Kurt Gödel, qui à 24 ans également (publication en 1931) a bouleversé tout l’édifice mathématique avec : Le premier théorème d'incomplétude qui énonce que :

tout système d’axiomes suffisant pour y démontrer les théorèmes de base de l'arithmétique est nécessairement incomplet, il y existe nécessairement et quoiqu’on fasse des énoncés qui n'y sont ni démontrables, ni réfutables.

La démonstration de Gödel est absconse et difficilement compréhensible[2].

Turing donne une démonstration d’une grande simplicité et d’une puissance logique phénoménale qui va entraîner la numérisation de la plupart des activités humaines.

La Science informatique était née, les forces productives de l’humanité et donc les sociétés humaines allaient connaître, avec la disposition des réseaux, une modification profonde, fondamentale, dans la façon de représenter le monde, communiquer et produire ; la Cybernétique[3] !

C’est l’illustration de la thèse de Marx sur « la science force productive directe ».

La MTU ou Machine de Turing Universelle :

C’est une machine séquentielle où le calcul est ramené à sa plus simple expression.

On peut schématiser comme suit une MTU : un ruban infini dans les deux sens divisé en cases. Dans chaque case un symbole et un seul. L’ensemble de ces symboles est l’alphabet extérieur et est la seule façon de communication entre la machine et le monde extérieur. Le bloc logique permet à la tête de lecture/écriture de lire, ou écrire sur le ruban en se déplaçant d’une seule case à la fois à droite ou à gauche. L’alphabet peut être réduit à sa plus simple expression comme ici (et comme dans nos ordinateurs), avec deux seuls symboles, mais on pourrait aussi utiliser les symboles ACGT et simuler ainsi le décodage de l’ADN ou de l‘ARN. Là est la puissance de simulation et calcul de la MTU

La MTU change notre vision du monde[4] L'informatique et la cybernétique n'ont de cesse d'aborder de nouveaux rivages et d'envahir de nouveaux domaines de l'activité humaine tout en exacerbant les contradictions d'un système basé sur l'exploitation de la force de travail humaine ainsi qu'une exploitation éhontée des ressources naturelles qui met en danger la pérennité d'une grande partie de l'humanité, l'industrie numérique lui donnant une dimension supplémentaire, et ce en un temps où la satisfaction des besoins de l'humanité pourrait être largement obtenue, le temps de travail aliéné drastiquement diminué et la nature préservée en utilisant précisément la Cyber-révolution mais dans un autre système de production et d'échanges.

Les machines à commande numérique[5], robots et autres cobots peuvent permettre l’émancipation humaine en la débarrassant du travail aliéné. Dans une machine à commande numérique, le programme de la MTU qui la commande n’est jamais que la traduction en langage de MTU de la gamme d’usinage chère aux ajusteurs et autres métallurgistes. Six cents ans avant notre ère, la démocratie grecque concernait 20.000 citoyens en s’appuyant sur 200.000 esclaves. Remplaçons les esclaves par des machines…

J’en appelle à Aristote : …Si donc il était possible à chaque instrument parce qu’il en aurait reçu l’ordre ou par simple pressentiment de mener à bien son œuvre propre, comme on le dit des statues de Dédale ou des trépieds d’Héphaïstos qui, selon le poète, entraient d’eux-mêmes dans l’assemblée des dieux, si, de même, les navettes tissaient d’elles-mêmes et les plectres jouaient seuls de la cithare, alors les ingénieurs n’auraient pas besoin d’exécutants ni les maîtres d’esclaves.

L’Informatique Avancée : l’I.A. que ces behavioristes d’anglo-saxons ont nommé Artificial Intelligence, que quelques grands communicants[6] francophones ont traduit par Intelligence Artificielle (sans avoir jamais traduit Intelligence service par service intelligent bien sûr) repose sur une algorithmique qui fait la part belle à l’apprentissage automatique et à de gigantesques bases de données pour une part importante de ses applications. Comme pour les algorithmes naturels[7] elle est basée sur le principe : Probablement Approximativement Correct (voir l’ouvrage éponyme de Leslie Valiant ed. Cassini 2019). Un autre concept a alimenté les fantasmes et les peurs relayés par la « grande » presse non spécialisée, c’est le concept de neurone[8] formel qui cherche à imiter le fonctionnement des neurones du cerveau. Faut-il pourtant rappeler ici qu’aucun avion ne vole comme un oiseau et que la « nature » n’a jamais inventé la roue ni le système bielle-manivelle[9] ? Le concept de neurone formel et des réseaux afférents n’est jamais que le concept de processus et de système distribué[10] adaptés à l’apprentissage. Chaque processus (« neurone ») étant une MTU, ou plutôt un PASC (Processus Asynchrone Séquentiel Communicant[11] ) qui a conduit à un cas particulier de MTU, une généralisation du concept en Machine Alpha concept de MTU communicante[12].

Les algorithmes de la nature, algorithmes naturels ou encore pour utiliser un terme plus spécifique écorithmes (Valiant déjà cité). En fait on peut traduire en termes algorithmiques la théorie de Darwin sur l’évolution ainsi que dans une certaine mesure l’épigénétique. Les mécanismes d’apprentissage de nature algorithmique déterminent le moteur de la vie sur Terre. Ces algorithmes sont exécutés dans des environnements inconnus, et c’est en interagissant avec l’environnement qu’ils apprennent à y agir avec efficacité, c’est-à-dire pour les êtres vivants à y vivre et s’y reproduire. Ils suivent un modèle d’apprentissage qu’on nomme écorithmes et qui ne sont pas le fait d’ordinateurs et dont on sait en fait peu de choses, ni d’où ils viennent, ni comment ils sont « inscrits » dans les organismes. Le cours de l’évolution est entièrement façonné par l’interaction des organismes avec leur environnement et leur adaptation à celui-ci qui est également susceptible d’évoluer à cause même de cette adaptation. Cette remarque sur l’adaptation des organismes au cours du temps conduit certains à poser l’égalité suivante : Biologie=Physique+histoire tant il est vrai que l’adaptation ne peut se faire que dans le cadre des lois physiques qui régissent tout phénomène dans la nature.

Plus prosaïquement, la plupart, pour ne pas dire tous, les comportements animaux ressortissent à des algorithmes. Ainsi au XVIe siècle, l’amiral Sir Francis Drake, dit « Le corsaire de la Reine » rapporte dans son journal de bord qu’alors qu’il mouillait dans la baie de San Francisco, le soir au fur et à mesure que la nuit s’installait, des lucioles s’allumaient en clignotant, par milliers puis par millions, transformant les falaises alentours. Petit à petit elles se synchronisaient et clignaient toutes en rythme… algorithme simple à reproduire, c’est un algorithme en deux phases délai et synchronisation.

Il en est de même du vol des oiseaux ou des bancs de poissons. L’activité d’un organisme en général et quel qu’il soit peut se résumer en trois grandes phases :

Communiquer ;
Calculer (avoir une activité « cérébrale » ou d’interprétation de signaux) ;
Agir suivant une procédure, (i.e. un algorithme).

Déjà toute activité qui peut ainsi se décomposer en phases puis en opérations élémentaires est susceptible de ressortir à une simulation/émulation algorithmique. Les algorithmes « en colonie de fourmis » ne me démentiront pas.

Ainsi un vol d’oiseaux migrateurs peut être décrit par un algorithme comme suit[13] :

séparation :
begin
- Se diriger sans trop s’approcher des voisins ;
End
Alignement
begin
- Se diriger dans le même sens que les autres ;
End
Cohésion
begin
- Se diriger vers une position moyenne vers le centre (le barycentre en fait) du groupe.
End

L’algorithmique, qu’on en soit ou pas conscient, est ainsi présente dans tout le monde effectif , celui qui fait et donc existe.

[1] A propos des algorithmes : https://www.youtube.com/watch?v=Xn0wuan_7-0

[2] On peut imager la démonstration par la contradiction suivante : Plus il y a de gruyère, plus il y a de trous ; plus il y a de trous, moins il y a de gruyère ; DONC plus il y a de gruyère, moins il y a de gruyère… Contradiction !

[3] Elle aussi vient de loin, c’est la science en grec ancien du pilotage des bateaux. C’est Norbert Wiener qui la remet au goût du jour en 1948, mais c’est la fusion avec l’informatique qui va en faire la force productive décisive du troisième millénaire de notre ère.

[4] Voir Cyber Révolution & Révolution sociale éd. Le temps des Cerises 2022

[5] En fait commandées par une MTU !

[6] Ou de chercheurs en quête de crédits !

[7] https://arxiv.org/abs/1304.5604

[8] Encore l’anthropomorphisme !

[9] Système décisif dans les machines à vapeur, qui transforme un mouvement linéaire en mouvement circulaire et vice-versa.

[10] Dont l’algorithmique est connue depuis plus d’une trentaine d’années (voir Algorithmique parallèle et distribuée

I. Lavallée, éd. Hermès 1990)

[11] ibidem

[12] voir hal-00814812v2 La machine α : 2013

[13] Craig W. Reynolds, « Flocks, herds and schools: A distributed behavioral model », ACM SIGGRAPH Computer Graphics, vol. 21, n^o 4,‎ juillet 1987, p. 25-34