Contribution de l’informatique théorique à la philosophie

Piste rouge Le 26 octobre 2015  - Ecrit par  Maurice Margenstern Voir les commentaires (2)

J’ai bien conscience que ce titre peut paraître prétentieux.

Ce que je souhaite, c’est attirer l’attention sur le fait qu’à mon humble avis,
un certain nombre de travaux de l’informatique théorique apportent un éclairage nouveau
sur des questions philosophiques.

Dans cette contribution, je n’en aborderai que deux,
le temps et le hasard.
Pour faciliter la compréhension, le premier paragraphe donne une description d’un
algorithme et de son exécution. Le second paragraphe discute des connexions entre
temps et algorithme et, notamment, quelle sorte de temps se dégage de l’algorithmique.
Le troisième paragraphe introduit la notion
d’objet aléatoire fini et fait le lien entre suites aléatoires et algorithmes.
Les paragraphes 2 et 3 permettent d’évoquer les notions de simulation et de codage
absolument fondamentales en informatique théorique que nous examinons au paragraphe 4
avant de les confronter aux mathématiques et à la biologie au paragraphe 5. En conclusion, je reviendrai sur le temps.

Les algorithmes

Les algorithmes séquentiels reposent sur une notion d’algorithme formel qu’il n’est pas
nécessaire de décrire précisément ici. Il suffit de savoir qu’un tel algorithme
est une suite finie d’instructions qui ne change pas au cours du temps et qui constitue une description de l’algorithme qu’on appelle aussi son programme. C’est une suite d’instructions, voir l’encadré ci-dessous, qu’on exécute une par une, dans l’ordre spécifié par les instructions elles-mêmes dans le but de résoudre toute instance d’un même problème. Ces instructions sont écrites d’une façon standardisée en permettant, en principe, l’exécution par une machine. Dans cette définition informelle, ce terme toute instance est important. Il indique qu’un algorithme est une solution d’un problème dont l’énoncé comporte en général des paramètres susceptibles de prendre un nombre infini de valeurs. En informatique théorique, les valeurs prises en considération sont toujours des entiers naturels. Un algorithme n’est pas un programme au sens des langages de programmation. Il y a deux différences importantes : un programme est réellement exécuté sur une machine ; les données d’un programme sont toujours finies et son résultat également, si résultat il y a. En effet, comme les algorithmes, les programmes peuvent ne pas terminer leur exécution sur une donnée. En général, un programme est l’implantation d’un ou plusieurs algorithmes. Accessoirement, les techniques de gestion des variables qui jouent un rôle important en programmation n’ont pas leur place en algorithmique où les variables sont toutes globales. La raison en est simple : le passage d’un argument n’a aucun sens si cet argument est un nombre dont l’écriture mesure une année-lumière. Par contre, une variable d’un algorithme peut prendre une valeur
nécessitant une écriture aussi grande : la seule restriction est celle qu’impose
le problème que l’algorithme est censé résoudre. Ainsi, un algorithme peut calculer tous les nombres premiers jusqu’à $10^{200}$ ce qu’aucun programme ne peut faire.

Algorithme :

Voici une ébauche de formalisation de la notion d’algorithme. Un algorithme
est une suite finie d’instructions $\cal I$, disons $I_1$, $\ldots$, $I_k$ et dans $I_j$
on dira que $j$ est le numéro de cette instruction.
Les instructions sont de cinq sortes :

  • les instructions élémentaires : elles indiquent une action de l’algorithme considérée comme primitive. ; quand l’action indiquée par l’instruction a été exécutée on
    passe ensuite à l’instruction suivante ;
  • les blocs : suite finie d’instructions ; les instructions sont exécutées l’une après l’autre dans l’ordre de la suite ;
  • les branchements conditionnels : ils sont de la forme si $C$ alors $B_1$ sinon $B_0$ finsi ; ; $C$ est une fonction prenant la valeur 0 ou 1 ;$B_0$ et $B_1$ sont des blocs ; si $C$ vaut 1, on exécute $B_1$, si $C$ vaut 0, on exécute $B_0$, on passe ensuite à l’instruction suivante ;
  • les boucles tantque : elles sont de la forme tant que $C$ faire $B$ fin ; ; $C$ est une fonction valant 0 ou 1 ; $B$ est un bloc ; le calcul de $C$ utilise des variables qui peuvent être modifiées par $B$ ; tant que $C$ vaut 1, on exécute $B$ ; quand $C$ vaut $0$, on exécute l’instruction suivante ;
  • l’instruction d’arrêt : quand l’exécution arrive à cette instruction, l’algorithme a terminé son travail.

On dit que les blocs, les branchements conditionnels et les boucles tantque sont des instructions structurées.

Ce qui est intimement lié au temps, c’est l’exécution de l’algorithme. On suppose qu’on dispose d’une horloge définissant un temps discret dont les instants peuvent être désignés par les entiers naturels, on parlera donc du temps $n$, l’instant associé au nombre naturel $n$. L’exécution de l’algorithme peut être représentée par une fonction $f$ du temps, donc définie sur un segment initial de $I\!\!N$, l’ensemble des nombres naturels.
La valeur de $f(n)$ est le numéro de l’instruction $I_j$ exécutée au temps $n$.
A chaque temps, l’algorithme exécute une instruction et une seule parmi les instructions
de $\cal I$. La fonction $f$ n’est là que pour donner une description mathématique
de la chose car ce que fait $f$ est défini par $\cal I$. En effet, toute instruction $I_j$
de $\cal I$ indique ce qu’on fait au temps considéré et quel est le numéro de l’exécution
exécutée au temps suivant. Ce numéro peut dépendre de la valeur $v_j$ d’un indicateur
au moment où l’instruction $I_j$ est exécutée, $j$ étant un entier appartenant à
l’intervalle $[1..k]$. On supposera que la dernière instruction du programme, $I_k$, est une instruction d’arrêt, voir encadré.
Si $I_k$ est exécutée, on dira que l’algorithme
s’arrête au temps où cette instruction est exécutée pour la première fois.
Souvent, la suite des $f(n)$ est appelée trace de l’exécution de
l’algorithme. On suppose, par convention, que l’algorithme commence son exécution au temps 0
et qu’il dispose d’une information dite donnée initiale qu’on peut supposer
représentée par un nombre naturel $d$. La fonction $f$ peut-être aussi bien
définie sur un intervalle $[0..t]$ avec $f(t)=k$ que sur $I\!\!N$ tout entier
avec $f(\tau)\not=k$ pour tout temps $\tau$. Dans le premier cas,
on dit que l’algorithme s’arrête au temps $t$, et que le résultat du calcul de $\cal I$
sur $d$ est la valeur au temps $t$, $r(t)$, d’une variable $r$ fixée une fois pour toutes, les
valeurs de $r$ pouvant être un nombre naturel quelconque. Dans le second cas, on dira que
l’algorithme ne s’arrête pas : à chaque temps, une instruction s’exécute et la suivante
n’est pas l’instruction d’arrêt.

Évidemment, on peut introduire une quantité phénoménale de remarques plus ou
moins métaphysiques à partir de cette notion d’instant 0. En particulier, ce qui
se passe avant n’entre pas dans le champ de l’algorithme qu’on considère. En fait,
sur un plan épistémologique, la construction de ce qu’on appelle une configuration
initiale, en quelque sorte la préparation des données sous une forme adaptée à
l’algorithme qui va les exploiter est en dehors du champ de l’exécution elle-même
mais peut faire l’objet d’une étude appropriée qui entre dans le champ de l’algorithmique car plusieurs algorithmes peuvent être mis en œuvre à cette occasion..

Cette description générale des algorithmes donnée au premier paragraphe montre que
l’exécution d’un algorithme n’est pas a priori réversible :
partant d’un temps $t$, d’un résultat $r$ et d’un programme $\cal I$, on ne trouve pas
toujours $d$ tel que l’exécution de $\cal I$ sur $d$ nous donne $r$ en un temps au plus $t$.
A priori, connaissant $r$, $t$ et $\cal I$, on finira par trouver $d$ tel que $r(t)=r$ et
que $f(t)=k$ si un tel $d$ existe, mais si $d$ n’existe pas, on ne pourra pas le constater parce
qu’il faudrait avoir épuisé toutes les possibilités, ce qui nécessite
un temps infini. Mais même dans le cas où, pour une raison particulière, on pourrait exclure
le cas infini, il se peut que plusieurs valeurs de $d$ donnent un même résultat en un
même temps de calcul. Mais même dans les cas où il n’y aurait qu’une valeur de $d$, la
procédure générale que nous avons décrite nécessite un temps de calcul incomparablement
plus grand que le calcul de $r$ par $\cal I$.

Sur de nombreux exemples, on peut constater que pour les algorithmes qui calculent la valeur
d’une fonction mathématique, leur exécution ne partage pas, en général, les
propriétés de la fonction. Ainsi, si la multiplication est commutative, les algorithmes de
la multiplication ne le sont pas : les exécutions de l’algorithme sur 2$\times$3 et de 3$\times$2 ne donnent pas lieu, en général, aux mêmes traces d’exécution de l’algorithme utilisé pour effectuer cette multiplication. Ces nombreux algorithmes effectuant même opération mathématique diffèrent non seulement par le codage des données, mais surtout par les calculs mis en œuvre.

Les algorithmes décrits par l’encadré sont ce qu’on appelle des algorithmes séquentiels déterministes. Il existe des algorithmes non-déterministes et des algorithmes parallèles Il n’y a pas de représentation générale d’algorithme parallèle. Il y a plusieurs notions de parallélisme et chacune induit une notion d’algorithme parallèle. Dans les algorithmes parallèles, il est souvent possible d’exécuter plusieurs instructions en même temps, il est possible aussi d’organiser l’espace pour exploiter les données et faciliter les calculs. À partir de ce que nous avons décrit ci-dessus, une façon d’obtenir un algorithme non-déterministe consiste à lever l’unicité de l’instruction suivante. Dans ce cas, la
fonction $f$ est beaucoup plus compliquée : à chaque pas on a un ensemble fini d’instructions
qui peuvent être exécutées. La bonne façon de représenter l’exécution est de
construire l’arbre des instructions possibles et l’exécution est alors un ensemble de chemins
dans l’arbre. Le calcul s’arrête si un des chemins conduit
à l’instruction d’arrêt et la valeur calculée est la dernière valeur prise par $r$ en
suivant ce chemin.

Les algorithmes et le temps

Le temps est une question bien délicate et il n’est pas question ici d’en donner
une définition. Nous nous contenterons de la notion intuitive de temps de tout un chacun, je pense qu’elle suffira pour illustrer ce propos.

La notion d’algorithme repose de façon essentielle
sur une notion de temps, qu’il s’agisse des traditionnels algorithmes séquentiels
ou des algorithmes parallèles que nous n’aborderons pas ici pour les raisons données plus haut.
La notion d’exécution est directement liée à une notion de temps et, comme on l’a vu,
il s’agit d’un temps discret et irréversible.
Il y a un avant et un après chaque instruction. Il y a plusieurs types d’instructions. Ce qu’on appellera les instructions d’affectation et les instructions structurées. Ces dernières sont le branchement conditionnel et la boucle contrôlée par une condition d’entrée, mais on ne précisera pas davantage ici ce que sont les instructions structurées.
Une instruction d’affectation est toujours de la forme $v := \kappa(w)$, où
$\kappa$ est une expression arithmétique et $w$ un ensemble de données pour la
fonction exprimée par $\kappa$. Quant à $v$, il s’agit de ce qu’on appelle une
variable. En informatique une variable n’est pas de même nature qu’une expression. En informatique, une variable désigne une place en mémoire identifiée par le nom de la variable : on dispose d’un dictionnaire qui, à chaque nom de variable associe la place en mémoire où on stocke la valeur de la variable. Une expression définit un calcul
qui est exécuté au moment où l’instruction est exécutée, fournissant une valeur.
L’exécution d’une instruction d’affectation induit un temps irréversible. Après
l’exécution de l’instruction, la valeur stockée dans la variable a en général changé.

On constate ainsi qu’au niveau local, celui de l’exécution d’une instruction d’affectation,
ainsi qu’au niveau global, celui de l’exécution d’un algorithme, l’exécution induit toujours
un temps irréversible. Il me semble que cette notion d’exécution, impossible à définir
formellement et telle que l’informatique nous la donne, éclaire cet aspect du temps qui nous
paraît irréversible. D’une certaine manière, cet éclairage semble indiquer que la
flèche du temps n’est peut-être pas aussi subjective qu’on pourrait le penser. Sur ce point,
le temps de l’informatique contredit la représentation du temps en mathématique : dans
les équations différentielles utilisées par la physique, le temps est essentiellement
réversible. Cela vient sans doute de ce qu’en mathématiques, le temps est une variable
réelle et non entière comme en informatique.

JPEG - 14 ko
Andreï Kolmogorov (1903-1987)

Les algorithmes et le hasard

JPEG - 27.9 ko
Richard von Mises (1883-1953)

Le hasard est une notion sans doute tout aussi complexe que celle du temps. Les années
trente du 20$^{\rm \grave eme}$ siècle ont connu un important débat sur la notion de
probabilité entre Kolmogorov et von Mises. Kolmogorov avait construit au milieu des années
vingt une axiomatique des probabilités toujours en usage aujourd’hui. D’un point de vue
épistémologique, il est intéressant de remarquer que cette axiomatique permet de manipuler
les probabilités mais ne dit absolument rien sur ce qu’elles sont, ni même comment on
peut calculer celle des événements de base : on en est réduit à l’inventaire des
méthodes utilisées traditionnellement. L’ambition de von Mises était de fonder la notion
de probabilité à partir de celle de fréquences.

Malheureusement, travaillant dans les années trente, von Mises ne disposait pas des notions qui auraient pu lui permettre de fonder
son approche. C’est au milieu des années soixante-dix qu’avec Chaitin et Kolmogorov [1], indépendamment l’un de l’autre et pratiquement simultanément, on a une approche
complètement nouvelle par la notion d’objet fini aléatoire. Intuitivement, un objet
aléatoire $K$ est un objet qu’il est plus simple de donner par son expression directe que
par un calcul. Prenons un exemple simple : une suite de 100 chiffres, zéro ou un, définie
par la répétition de la séquence 1001 n’est certainement pas aléatoire. Une
suite $s_{100}$ de 100 chiffres aléatoires sera donc une suite telle que tout algorithme
de calcul de $s_{100}$ est plus compliqué à écrire que la suite $s_{100}$ elle-même. On
peut définir la complexité algorithmique d’un objet $K$. Pour cela, on fixe une
représentation des algorithmes, mais il n’est pas possible ici de donner plus de détail. La
représentation est un mot dans un certain alphabet fixé une fois pour toutes. On dit alors
que la complexité d’un objet $K$ est $\kappa$, la taille du plus petit algorithme universel qui
permet de calculer $K$ à partir de 0. Pour un objet aléatoire, $\kappa\geq \vert K\vert$,
où $\vert K\vert$ est la taille de la représentation de $K$ lui-même. On peut alors
définir une notion de complexité sur laquelle va se fonder une définition des probabilités.
Il n’est pas possible de donner ici davantage de détail.

JPEG - 46.9 ko
Gregory Chaitin (1947- ...)

Mais ce qu’on peut comprendre ici, c’est que telle qu’elle vient d’être définie, la
notion de complexité est en relation avec la notion de compression. Si un algorithme
de calcul $\kappa$ permet de calculer$K$ à partir de 0 et si
$\kappa< \vert K\vert$, on dira que $\kappa$ est une compression de $K$.
Ainsi, une donnée aléatoire est une donnée incompressible.

Une autre approche, par les statistiques, conforte cette approche algorithmique.
Classiquement, une suite aléatoire est une suite qui échappe aux tests statistiques. Un tel
test est par définition une fonction. Tout le problème dans cette approche est de trouver
un ensemble de tests qui ne soit ni trop gros, aucune suite n’est aléatoire, ni trop petit,
toute suite est aléatoire.

JPEG - 24 ko
Per Martin-Löf (1942-...)

Martin Löf, élève de Kolmogorov, a découvert à la fin des années soixante-dix que si on prend pour tests statistiques
ceux qui sont récursifs, autrement dit ceux qui se calculent par un algorithme dont l’exécution se termine toujours, alors
l’ensemble des suites aléatoires n’est pas trivial.

Ainsi, là encore, les algorithmes apportent un éclairage nouveau à des notions
fondamentales des mathématiques et, dans une certaine mesure aussi à la notion philosophique
de hasard.

Simulation et codage

On peut remarquer que chacun des deux paragraphes ci-dessus fait écho à un des deux
concepts clés de l’informatique : la simulation et le codage.

L’exécution d’un algorithme est très étroitement liée à la notion de simulation.
Nous ne définirons pas formellement cette notion. C’est pratiquement impossible à faire
et, pourtant, tout le monde comprend ce qu’on entend par là. Si on tente de circonscrire
cette notion, l’exécution d’un algorithme est un bon outil d’analyse. En effet, la simulation fait référence à deux processus qui se déroulent et que l’on compare. Et c’est cette comparaison qui va nous dire si un des deux processus simule l’autre. Cette comparaison va porter sur les pas d’exécution des algorithmes s’il s’agit de processus algorithmiques ou représentables par des algorithmes. La comparaison repose sur l’analyse des instructions dont les actions élémentaires ne sont pas en général les mêmes, ce qui fait qu’un pas d’exécution d’un algorithme peut en nécessiter plusieurs par celui qui simule son exécution.

Lorsqu’on parle de codage, tout le monde a en tête les divers protocoles de sécurité des réseaux, quelle que soit leur nature. Les codages utilisés pour des impératifs de sécurité sont un cas très particulier d’une notion plus générale.

En fait, le langage naturel lui-même, qu’il soit oral ou écrit, est un codage.
Avant toute chose, un codage est la mise en œuvre d’un système de compression de l’information. Les mots d’une langue renvoient toujours à une réalité beaucoup plus riche que les sons eux-mêmes de ce mot ou encore que son écriture dans un système fixé. On peut considérer que le langage naturel est en quelque sorte un codage initial. Ce que nous appelons codage se greffe sur le codage initial constitué par le langage.

La notion de compression est toujours à l’œuvre dans cette nouvelle acception du
codage, mais s’y ajoute la complexité : de ce point de vue, les différents codages n’ont
pas tous les mêmes caractéristiques. Mais vues sous cet angle, les
propriétés des codages vont montrer leur lien avec le calcul et donc les algorithmes.
On peut le voir sur cette propriété des codages : étant donné un alphabet fixé d’au moins
deux lettres, on peut y coder les lettres de n’importe quel autre alphabet fini. Cette
capacité des codages à coder des alphabets plus gros que celui qu’utilise le codage
considéré est souvent à la base des algorithmes de simulation : on commence
par définir un codage de ce qu’on simule pour définir précisément l’algorithme
de simulation. Ce concept de simulation est à la base de résultats importants en
théorie de la calculabilité, en particulier sur les théorèmes d’universalité.
L’existence d’algorithmes universels n’est pas autre chose que la possibilité de construire un algorithme qui peut simuler n’importe quel algorithme, y compris lui-même bien sûr. De nombreux théorèmes de complexité se démontrent par simulation d’un algorithme
d’une classe de complexité donnée par un algorithme d’une autre classe dans le cas où une
telle simulation est possible. Une autre illustration de la notion de simulation dans son aspect
universalité est fournie par les compilateurs. Ces objets ont été à la mode, y compris
pour le grand public dans les années quatre-vingt. Aujourd’hui, ils sont passés de mode
mais ils sont toujours présents. Ils sont cachés dans les systèmes d’exploitation actuels
et ce sont toujours des compilateurs qui permettent de mettre au point les applications connues
du grand public, même ce qu’on peut avoir maintenant sur un téléphone portable ou un
smartphone. Le fait qu’on peut faire sur un smartphone ou sur une tablette ce qu’on fait sur un ordinateur et inversement, n’est qu’un aspect visible du concept d’universalité qui est au cœur de la notion d’algorithme et qui explique leur phénoménal pouvoir de simulation.

PNG - 603.9 ko
Kurt Gödel (1906-1978)

Pour revenir au codage, on peut illustrer
ces questions de complexité susceptibles de différentier les codages sur
un codage célèbre que les mathématiciens aiment beaucoup : le codage des suites finies d’entiers naturels par les entiers naturels que Gödel a construit. Le codage repose
sur la propriété de l’unicité de décomposition des entiers naturels en facteurs
premiers. Le codage est défini de la façon suivante. On désigne par $\{p_i\}_{i\in I\!\!N^+}$
avec $p_1=2$, $p_2=3$, $\ldots$ la suite des nombres premiers. À la suite finie
$(x_1,\ldots,x_n)$ on associe
$p_1^{x_1}\ldots p_{n-1}^{x_{n-1}}p_n^{x_n+1}-1$, le code 0 étant celui de la suite vide. Il est nécessaire de faire ces petites modulations
sur les exposants et d’introduire ce terme $-$1 pour avoir une bijection qui tienne compte aussi
des suites de $k$ zéros [2]. Ce codage est très élégant d’un point de vue mathématique
mais absolument inefficace sur un plan pratique : en effet, la taille du code est au moins
exponentielle par rapport à la donnée, ce qui est plutôt fâcheux.

Une solution plus économique et
qui n’est pas dénuée d’attrait est le codage de Quine. On écrit les termes de la suite
$(x_1,\ldots,x_n)$ en binaire, soit donc $c_i$ l’écriture binaire à la Quine de $x_i$, 0 étant représenté par $c_0$ qui est le mot vide. Le nombre 0 est le code de la suite $(0)$. Quand la suite $(x_1,\ldots,x_n)$ n’est pas $(0)$, son code est le nombre
qui s’écrit $c_12\ldots2c_n$ en base 3 de Quine. En taille de l’écriture des nombres
$x_1$, $\ldots$, $x_n$ qu’on suppose dans la base 2, ce codage est polynomial.

Mathématiques, informatique, biologie

Simulation et codage sont deux notions également à l’œuvre dans une science en pleine évolution : la biologie. C’est aujourd’hui un truisme de dire que ces notions sont
à l’œuvre aussi bien à l’échelle moléculaire qu’à l’échelle macroscopique.
Tout autant que les mathématiques, l’informatique aspire à fournir des modèles efficaces pour l’étude du vivant. Même si les biologistes à l’heure actuelle préfèrent utiliser des équations aux dérivées partielles plutôt que des algorithmes, on me permettra de penser que l’avenir pourrait voir les choses s’inverser.

À mon sens, la raison de fond de cette inversion réside dans la remise en cause d’une
conception des lois de la nature qui a dominé la science jusqu’à maintenant et qui me
paraît erronée. La conception dont je parle, de plus en plus combattue, est encore partagée par beaucoup. C’est une vision des sciences
à la manière des poupées russes : les mathématiques gouvernent les lois de la physique lesquelles gouvernent les lois de la chimie lesquelles, à leur tour gouvernent celles de la biologie. On peut bien entendu continuer cette série jusqu’aux sciences humaines. Pourtant, si je dis que pour comprendre des phénomènes de psychologie il faut en revenir aux équations
aux dérivées partielles qui, d’après le schéma ci-dessus gouvernent les neurones,
je pense que peu de personnes me prendront au sérieux et elles auront raison. Je prendrai
un exemple moins évident : on peut encore lire ici ou là que pour comprendre le fonctionnement d’un ordinateur, il faut connaître les lois de l’électro-magnétisme.
Tout dépend de quoi on parle : s’il s’agit du fonctionnement de la machinerie électronique,
la réponse est oui. S’il s’agit du fonctionnement du système d’exploitation, la réponse
est non. Sans système d’exploitation, un ordinateur n’est qu’une machine
inutilisable [3].

Mieux, le fonctionnement de base d’un système d’exploitation n’est pas dépendant de
l’électronique : on pourrait faire la même chose, mais pas dans le même temps, avec des
aiguilles à tricoter et des fiches perforées, ou bien avec des circuits pneumatiques ou même
avec une locomotive parcourant un circuit de chemin de fer, sans compter les essais faits
actuellement avec un certain
succès sur des brins d’ADN. Si aujourd’hui on utilise l’électronique, c’est parce que cette
technologie est la seule à l’heure actuelle à permettre la mise en œuvre des algorithmes
avec la rapidité et la fiabilité qu’on connaît.

Pour revenir aux lois de la nature, il faut sérieusement moduler
cette vision hiérarchique des sciences. La biologie me paraît être un domaine où
codage et simulation sont à l’œuvre de façon aussi forte qu’en informatique. L’étude
actuelle des génomes en est une illustration éclatante. Mais il y a d’autres exemples
qui sont tous à la base d’un phénomène singulier : pour l’instant, l’informatique
trouve une source d’inspiration très féconde dans la biologie. De nombreux phénomènes
biologiques peuvent être analysés en termes de paradigmes de calcul et du coup, ils
sont souvent, sous une forme très abstraite, utilisés en informatique théorique
comme modèles de calcul. On peut citer, dans le désordre, les automates cellulaires,
les algorithmes génétiques, les systèmes à membranes, les modèles de colonies de
fourmis. Il est certain que le vivant se manifeste dans des conditions
physiques et chimiques qui sont loin d’être arbitraires. Mais une fois
ces conditions observées, les lois du vivant sont elles toujours déterminées par les lois de la physique et de la chimie ?
Il me semble que la réponse serait plutôt négative. Il me semble que c’est ce que montre cette floraison de modèles,
tous fondés sur des observations bien réelles. Les notions d’information,
de représentation de l’information et des modalités d’échange de l’information
jouent certainement en rôle capital au niveau du vivant et elles ne sont pas réductibles aux schémas classiques offerts par l’analyse mathématique.

Ceci peut nous permettre de revenir à cette différence de traitement du temps en
mathématiques et en informatique. Le temps n’intervient pas en mathématique. La vérité des théorèmes ne change pas, même si l’évolution des mathématiques dans le temps peut conduire à des modifications dans le champ de validité des théorèmes, en général vers une certaine extension de ce champ, parfois vers une restriction. De ce point de vue, le
temps opère sur les
mathématiques en tant que produit de l’activité humaine, mais cette intervention du temps
n’est pas internalisée dans les mathématiques, en tout cas pas dans celles qui sont
pratiquées par l’immense majorité des mathématiciens. Il n’en va pas de même en informatique
même théorique où le temps est toujours présent par l’intermédiaire de l’exécution
des algorithmes. Tout algorithme a vocation à s’exécuter, même s’il s’agit d’un algorithme
si compliqué ou si lent qu’il n’est d’aucun intérêt pratique actuellement [4]. En fait, quand on
parle du temps représenté par une variable réelle, il s’agit du temps en physique
qui utilise un concept mathématique, celui de variable réelle, pour représenter le temps.
En informatique, le temps des algorithmes est un temps discret, et même si les algorithmes
temporels utilisent un temps apparemment continu, les impératifs d’effectivité transformeront
ce temps en temps rationnel, voire en temps discret. On peut aussi remarquer à ce sujet
que si les langages de programmation connaissent les réels machine, ces objets ne sont
que des codages, en nombres entiers, d’approximations rationnelles de nombre réels.
Les approximations en question sont très grossières d’un point de vue théorique mais souvent suffisantes d’un point de vue pratique : souvent mais pas toujours. Les problèmes de retenue
que les mathématiciens connaissent sous le nom d’explosion numérique ne sont qu’une variante
en termes de nombre réels de l’indécidabilité du problème de l’arrêt, une conséquence
aussi de l’universalité.

Retour sur le temps pour terminer

Il me semble que les questions que j’ai abordées ne font pas l’objet d’un consensus ni parmi les philosophes, ni parmi les scientifiques. Pour comprendre ce que j’appelle consensus, je prendrai l’exemple de la rotondité de la Terre que plus personne ne remet sérieusement en question. Y a-t-il consensus sur le temps ? Il me semble que non. Son irréversibilité est assurément une donnée intersubjective. Partagée par tous les humains ? Dans toutes les civilisations et dans toutes les cultures ? Quant au temps
du monde physique, les choses sont bien peu assurées. Rappelons l’expérience de pensée de Zénon dans laquelle Achille dispute une course avec la tortue. Comme il
est réputé bien plus rapide, Achille donne à la tortue une avance, disons d’une centaine de mètres. Quand il aura parcouru cette distance, la tortue aura avancé d’une nouvelle distance et lorsque Achille aura parcouru cette nouvelle distance, la tortue aura encore avancé et ainsi de suite, de sorte que jamais Achille n’a pu rattraper la tortue. C’est ce que disait Zénon selon ses adversaires [5]. Les solutions mathématiques trouvées par la notion de limite d’une suite et donc d’une série au 18$^e$ et au 19$^e$ siècles ne répondent pas à la question. En effet, le raisonnement de Zénon suppose une division à l’infini réelle du temps et de l’espace. On peut bien-sûr effectuer cette division par la pensée. Peut-il en être ainsi dans la réalité ? Si on pense qu’il en est ainsi, le raisonnement est correct. Cependant, même dans ce cas il y a une difficulté : si on peut concevoir une division à l’infini, aucun être humain ne peut accomplir une infinité d’actions, ce que supposerait l’adéquation du schéma de pensée à la réalité dans cet exemple précis car nul ne conteste qu’Achille rattrape la tortue [6]. Que doit-on en conclure ? On ne sait pas ce que Zénon en concluait [7]. On sait par contre, que Démocrite et son maître Leucippe, ce dernier fut un disciple de Zénon, sont les auteurs d’une conception atomique de la matière qui a connu un certain succès quelque deux mille cinq cents ans plus tard. Comme il semble y avoir un consensus sur le fait qu’Achille a bien rattrapé la tortue [8], on en conclut, moyennant cette intime connexion du temps avec l’espace dans le mouvement, que le temps et l’espace sont discontinus.

En conclusion, il me semble que ce temps discret et irréversible de l’informatique théorique n’est peut-être pas une si mauvaise abstraction de la réalité. Plus mauvaise que ce temps continu et réversible que les mathématiques ont donné à la physique ? À vous d’en juger.

Post-scriptum :

Pour en savoir plus, n’hésitez pas à visionner en ligne la captation audiovisuelle de cette séance du Séminaire d’histoire des mathématiques de l’IHP.

L’auteur adresse ses plus vifs remerciements aux organisateurs de cette journée,
Liesbeth De Mol et Maarten Bullynk pour l’avoir invité à participer à la table ronde de la séance ’les maths face à l’ordinateur’ du séminaire d’IHP. Il tient aussi à remercier Frédéric Brechenmacher pour son aide technique et pour les photos illustrant cet article.

L’auteur et la rédaction d’Images des Maths remercient également les relecteurs Marc Jambon, Leroy, Maxime Bourrigan et Emmanuel Beffara pour leur relecture attentive et leurs remarques constructives.

Article édité par Frédéric Brechenmacher

Notes

[1Il s’agit du même Kolmogorov des années vingt qui, près de cinquante ans après,
est revenu sur la théorie qu’il avait fondée : cas peut-être unique dans l’histoire des
sciences.

[2Merci à Marc Jambon pour une précision donnant un codage vraiment bijectif.

[3On rejoint ici ce que nous avions dit au sujet du parallélisme. Il existe
des machines parallèles. Dans le meilleur des cas elles sont utilisées bien en dessous de leurs
possibilités. Pourquoi cette sous-utilisation ? Tout simplement faute de théorie adéquate
pour représenter les calculs qu’une telle machine peut effectuer. Rappelons également que la théorie a précédé la construction des ordinateurs : la machine de Turing date de 1936, chronologiquement antérieure à 1945, date de la construction du premier ordinateur.
A méditer par tous ceux qui considèrent que les recherches théoriques ne servent à rien.
Méditation sur cette
méditation : il ne sert à rien de vouloir anticiper sur les résultats de recherches
théoriques. L’inconnu est nécessairement imprévisible : sinon, il ne serait pas aussi
inconnu...

[4Il faut
se méfier d’exclusions catégoriques : certains algorithmes de l’addition inventés dans
les années soixante et jugés en leur temps fantaisistes sont utilisés dans les processeurs
depuis la fin des années quatre-vingt-dix. La technologie des années quatre-vingt-dix
a permis de rendre effectifs ces algorithmes jugés en leur temps fantaisistes. Ils se sont avérés plus efficaces que les algorithmes utilisés jusque-là.

[5Personne ne sait ce qu’a dit Zénon exactement, et surtout, personne ne sait ce qu’il concluait de ses raisonnements.

[6De même qu’en algorithmique on ne se pose pas la question de la correction d’un algorithme puisque c’est une solution d’un problème, ce qui n’est pas le cas d’un programme où la question de la correction du programme est en fait indécidable, on suppose qu’Achille veut vraiment rattraper la tortue et qu’il court suffisamment vite pour le faire.

[7Peut-être Zénon était-il déjà dans la position de Lewis Carroll qui, dans son texte Ce que la tortue dit à Achille pose un problème qu’il ne résout pas. Bertrand Russell, qui résolut le problème, apporta au crédit de Lewis Carroll d’avoir posé correctement le problème. Il me paraît douteux de croire que Zénon feignait d’ignorer qu’Achille rattrape la tortue : n’oublions pas que les Grecs connaissaient le raisonnement par l’absurde à l’époque de Zénon.

[8Le texte de Lewis Carroll que je mentionne est un dialogue entre Achille et la tortue une fois que celle-ci a été rattrapée par Achille.

Partager cet article

Pour citer cet article :

Maurice Margenstern — «Contribution de l’informatique théorique à la philosophie» — Images des Mathématiques, CNRS, 2015

Crédits image :

Image à la une - Mathématicien Andreï Kolmogorov, image issue du site ChronoMath.
img_14242 - amilienalbum der Familie Gödel, Scan from Gianbruno Guerrerio, Kurt Gödel - Logische Paradoxien und mathematische Wahrheit, S.24
img_14241 - http://www.ae-info.org/ae/User/Martin-L%C3%B6f_Per
img_14240 - cs.auckland.ac.nz
img_14239 - http://www.pms.ru/
img_14238 - Konrad Jacobs, Erlangen — http://owpdb.mfo.de/detail?photo_id=2896

Commentaire sur l'article

  • Temps et algorithmes — Informatique théorique et nombres entiers — Algorithmes récursifs

    le 2 novembre 2015 à 10:45, par Pierre Lescanne

    Votre article pose plusieurs problèmes intéressants sur le temps, l’aléatoire et la complexité et leur liens avec l’informatique théorique, mais je ne voudrais parler ici que du temps, que vous fondez sur une notion très restrictive d’algorithme, plus ou moins apparentée à celle de machine de Turing. Or cette dernière notion est loin d’être la seule, ni même la première historiquement. Car Turing et sa machine n’arrivent qu’après Church et son λ-calcul et Herbrand et Gödel et leur théorie des fonctions récursives générales. Le λ-calcul, qui décrit parfaitement les algorithmes et par rapport auquel Turing lui-même a montré l’adéquation de son modèle, est très bien représenté par les langages de programmation OCAML ou HASKELL. En revanche, comme les fonctions récursives générales, il décrit les calculs sans en donner l’ordonnancement. Cela est fort heureux à plus d’un point de vue. N’ayant aucune notion d’avant ou d’après, il est par conséquent impossible de définir à partir du λ-calcul ou de la théorie des fonctions récursives générales une flèche du temps et d’affirmer que l’informatique théorique et pour être plus précis la théorie de la calculabilité contribuent à élaborer un concept de temps.

    Il y a deux autres affirmations sur lesquelles nos positions divergent aussi.

    * « En informatique théorique, les valeurs prises en considération sont toujours des entiers naturels. » Il me semble que vous oubliez les booléens (avec leurs deux valeurs vrai et faux représentées par 0 et 1) sur lesquels le codage des entiers est fondé généralement. Vous oubliez aussi les structures de données : arbres, graphes, machines abstraites, suites finies ou infinies etc. sur lesquelles travaillent beaucoup d’algorithmes. Votre affirmation est d’autant plus piquante que l’article fondateur de Turing sur les machines abstraites, qui portent maintenant son nom, traite des nombres réels calculables comme l’indique son titre Sur les nombres calculables avec une applications au problème de la décision, les nombres calculables en question étant les nombres réels.

    *La définition que vous donnez de la récursivité à savoir que « [les algorithmes] récursifs [sont] ceux qui se calculent par un algorithme dont l’exécution se termine toujours » ne ferait pas l’unanimité dans la communauté de l’informatique théorique. En ce qui me concerne je vois plutôt un algorithme récursif comme un algorithme qui s’invoque lui-même, la récursivité étant la clé des modèles de calculs, autrement dit des formalisations d’algorithme, que je viens d’évoquer.

    Répondre à ce message
  • Contribution de l’informatique théorique à la philosophie

    le 2 novembre 2015 à 16:38, par Pauline

    C’est d’un niveau assez élevé, moi qui commence à étudier les mathématiques à travers des algorithmes des lois de poissons, je me sens un peu perdu, mais ça me motive vraiment à creuser ces théories.

    Merci

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM