L'irréductibilité computationnelle

J'ai parlé dans un article précédent du jeu de la vie de John Conway.
Pour certaines formes périodiques connues du jeu de la vie (les vaisseaux, les oscillateurs etc.), on peut prévoir quelle sera leur évolution.

Mais pour certaines configurations initiales, on ne peut pas prévoir si la forme va finir par se stabiliser, osciller ou disparaître. Il est impossible de prévoir leur évolution. On ne sait pas dire si la configuration atteindra l'un ou l'autre de ces stades, ni si elle le fait, au bout de combien de générations. On peut démontrer que connaître l'évolution ultime des certaines configurations initiales fait partie de la catégorie des problèmes mathématiques indécidables: il n'existe aucun algorithme capable de prévoir si une configuration initiale va s'éteindre ou si elle va conserver des cellules indéfiniment.
D'autre part, on peut montrer que pour certaines conditions initiales, on ne peut pas prévoir leur évolution, ni leur forme à la Nième génération, sans passer par les N-1 étapes précédentes.
Autrement dit, pour prévoir l'évolution du système, il faut simuler toutes les étapes intermédiaires. Il n'existe pas pour ces conditions initiales, de raccourcis qui permettent de prévoir leur évolution: c'est le problème de l'irréductibilité computationnelle.

Il ne s'agit pas d'une imprévisibilité théorique, puisqu'on peut toujours simuler l'évolution du système, mais il s'agit bien d'une imprévisibilité pratique puisqu'elle implique de passer par chacune des étapes une à une, sans pouvoir couper court pour aller plus vite. Une telle simulation peut prendre alors un temps qui excède nos capacités pratiques, ou à minima, prendre un temps équivalent à l'évolution du système lui-même, ce qui revient, dans certains cas, à une imprévisibilité de fait.

De manière plus générale, on ne peut pas prédire ce qui va émerger d'un phénomène d'auto-organisation car il existe des multiples attracteurs pour un système complexe, et la convergence d'un tel système vers l'un ou l'autre de ces attracteurs dépend d'une précision dans les conditions initiales qui nous est inaccessible (contrairement au jeu de la vie dont les règles sont parfaitement déterministes et dont on peut connaître les conditions initiales de manière précise).

On peut en tirer une philosophie évidente de l'action: pour certains types de questions, si on n'essaie pas, on ne saura jamais: la modélisation ne sert parfois à rien, sinon à justifier nos préférences intuitives.
Pour certains domaines, l'intuition, le hasard, l'empirisme sont nos seuls guides. Se tromper fait partie des règles du jeu. Tout l'art consiste alors à atténuer les conséquences d'une erreur, et à apprendre de ces dernières...