Dans la partie précédente, nous avons évoqué le fait que les automates cellulaires ont la même puissance de calcul que les machines de Turing. Nous allons maintenant étudier cette propriété de calculabilité d’un point de vue formel et nous intéresser aux définitions mathématiques qui sont nécessaires pour exprimer la propriété de calculabilité. Il est clair que certains automates cellulaires possèdent la capacité de calcul universel et que d’autres en sont dépourvus[24]. Les questions posées au sujet de la calculabilité se traitent en termes similaires pour les machines de Turing et pour les automates cellulaires. Ceci ne doit pas nous surprendre car un automate cellulaire réagit de la même façon qu’une machine de Turing, la différence fondamentale étant que toutes les cellules de l’espace cellulaire peuvent être actives et changer d’état, alors que dans une machine de Turing (M.T), seule la tête de lecture possède la capacité de changer l’état d’une cellule. En revanche, nous verrons que les automates cellulaires enrichissent le domaine d’étude des M.T en posant la question de la constructibilité universelle. Qualitativement, cette question se pose en ces termes : Est-il possible de concevoir un ‘constructeur’ tel que, si l’on lui ‘donne’ une description complète d’une configuration à obtenir, cette configuration soit ‘construite’ en un nombre fini d’étapes ?
Il a déjà été prouvé de façon constructive que divers modes de calcul réalisent la condition de calculabilité universelle [Odifreddi89], citons par exemple :
· les définitions de fonctions par machines de Turing,
· la récursivité générale,
· le lambda-calcul,
· les définitions de fonctions par système formel[25],
· les systèmes de réécriture de Post.
Von Neumann, puis Codd ont élargi cette liste en prouvant de façon constructive l’équivalence de la puissance de calcul des machines de Turing [Turing36] et des automates cellulaires. Le choix des machines de Turing est assez naturel : dans une telle machine les informations sont stockées sur un ruban subdivisé en cases ; il y a donc une certaine « proximité » avec le modèle des AC. Il est clair que le principal obstacle à l’établissement de la démonstration d’équivalence provient de ce que le fonctionnement des automates cellulaires est parallèle alors que celui des machines de Turing est séquentiel. Une machine de Turing permet en effet de suivre l’évolution de la machine et de son ruban pas par pas, à chaque étape seule une case du ruban peut être modifiée. Dans l’univers des AC, il n’est pas directement possible de suivre les modifications puisque à chaque étape toutes les cellules ont la capacité changer d’état. Pour montrer qu’à toute machine de Turing peut être associée un automate cellulaire équivalent, il va donc nous falloir « désactiver » le parallélisme. Ceci ne présente pas d’obstacle majeur mais conduit, si l’on s’y prend de façon « brutale », à utiliser un grand nombre d’états différents, limitant par-là l’intérêt d’utiliser des AC comme modèle. On comprend dès lors la difficulté à prouver de façon constructive l’existence d’un calculateur universel qui n’utilise qu’un nombre restreint d’états : 29 pour von Neumann, 8 pour Codd. Ces deux démonstrations sont assez longues, la construction de von Neumann [vonNeumann66] étant difficilement compréhensible dans sa totalité, celle de Codd étant plus accessible [Codd68]. Nous ne chercherons pas ici à expliquer comment on peut effectivement construire une machine dotée de la capacité de calculabilité universelle dans un univers cellulaire et nous recommandons au lecteur intéressé de se reporter à [Codd68] ; par contre, nous pouvons concentrer notre attention sur les définitions fondamentales qui précèdent la démonstration. Ces définitions sont en effet les briques élémentaires qui vont permettre que le domaine, nouveau pour l’époque, des automates cellulaires gagne le statut de domaine autonome. Pour reprendre la terminologie de Kuhn, on dira que ces définitions sont l’acte de naissance d’un nouveau paradigme [Kuhn70].
Nous considérons une machine de Turing T qui opère sur une bande bi-dimensionnelle, ceci pour faciliter la correspondance entre les deux modèles. Soit T l’ensemble des bandes qui contiennent seulement un nombre fini de symboles non vides et W l’ensemble des symboles utilisés dans T. Une fonction partielle ? est dite calculable par machine de Turing, s’il existe une machine de Turing munie de l’alphabet W qui calcule ?.
La première étape dans la démonstration de l’équivalence M.T / A.C consiste à associer l’espace des bandes T à l’espace cellulaire Z muni de configurations totalement passives. Nous retrouvons là le fait que les cellules des configurations totalement passives sont de simples supports de l’information.
On dira alors que la fonction ? est calculable dans Z SSI il existe :
une configuration c, une cellule a ? sup(c) et un état v différent de l’état de repos - qui correspond à l’état d’arrêt de la M.T - , tels que :
pour toute configuration d ? T, il existe un temps t pour lequel :
(A) Ft( c U d) / sup(T) = ?(d) avec sup(T)= U sup(d), d ? T
(B) Ft(c U d)(a) = v
(C) Ft’(c U d)(a) ? v, pour tout t’< t.
Cette définition peut sembler à première vue assez compliquée. Analysons donc la signification des conditions (A), (B) et (C) à l’aide du tableau suivant :
Machine de Turing |
Automate cellulaire |
| état de la machine et de la bande | cellules dans un certain état |
| état d’arrêt qui marque la fin du calcul | activation d’une cellule a dans un état v pour marquer la fin du calcul |
| bande bidimensionnelle | sup(T) |
| état initial de la bande | configuration d |
| tableau de marche de la MT | configuration c |
Il apparaît alors que :
(A) signifie que ?(d) a effectivement été calculée,
(B) signifie que l’état de fin de calcul a été atteint au temps t,
(C) signifie que l’état de fin de calcul n’a jamais été atteint avant le temps t.
Codd peut alors définir deux concepts dérivés du concept de calculabilité pour les AC. Nous commençons par définir la translation de configuration :
On dira que s’ est une translation de la configuration s SSI il existe un élément d ? I x I tel que
s’(a) = s( a + d) pour tout a ? I x I , qu’on notera s’= sd en abrégé.
On dira d’un espace cellulaire qu’il possède la propriété de calculabilité universelle si pour toute fonction calculable par M.T ?, il existe une configuration c qui calcule ?, au sens défini précédemment. S’il existe une configuration c telle que :
pour toute fonction calculable par M.T ?, il existe une bande d ? T et une translation d telle que dd est disjointe de T et de c , et telle que c U dd calcule ?,
alors cette configuration c sera qualifiée de calculateur universel.
Nous venons de définir l’équivalent de la machine de Turing universelle dans le domaine des automates cellulaires[26]. Nous verrons dans les chapitres qui suivent que cette notion se place cœur d’une épistémologie des automates cellulaires.
Nous pouvons désormais utiliser la spécificité des automates cellulaires pour enrichir notre capital de définitions : il s’agit de définir la propriété de constructibilité. Une configuration donnée peut en effet évoluer en conduisant à la création d’autres configurations, lesquelles configurations vont à leur tour pouvoir évoluer librement dans l’espace cellulaire. Si on fait l’analogie « configuration = objet » la notion de constructibilité devient proche du concept de production. Il devient possible de poser des questions telles que : « A quelle condition un objet X peut-il être produit par un objet Y ? ». Codd propose de formaliser cette question comme suit :
c et c’ étant deux configurations, on dira que c construit c’ SSI il existe un temps t pour lequel :
· c’ est une sous-configuration de Ft(c) disjointe de c
· ( Ft(c) - c’ ) ne passe pas d’information à c’.
En clair, la configuration construite (l’objet construit) doit être construite à l’extérieur de la configuration initiale(le constructeur). Par ailleurs, une fois terminée l’étape de construction de l’objet construit, il ne doit y avoir aucune interaction entre le constructeur c et l’objet construit c’ : l’évolution de c’ doit se faire identiquement selon que c est présente ou non. Cette contrainte est une contrainte très forte, qui élimine de nombreux cas d’auto-reproduction triviale. Ceci correspond bien à l’idée que nous nous faisons d’une machine-outil : celle-ci conduit à l’élaboration d’autres objets (éventuellement des constituants de machines-outil) qui deviennent alors indépendants de la machine qui les a créés.
La propriété de construction universelle requiert qu’un espace cellulaire puisse accueillir un ensemble de configurations C qui calcule toute fonction calculable par machine de Turing. On dira que C est un ensemble complet de calculateurs s’il existe une configuration cu tel que toute configuration c de C puisse être construite par adjonction de configurations disjointes de C, alors cu est appelé un constructeur universel et l’espace accueillant cu est dit posséder la propriété de constructibilité universelle[27].
Nous approchons du problème central de l’auto-reproduction, tel que von Neumann l’a posé, à savoir un automate peut-il construire un autre automate, et particulièrement peut-il construire un automate similaire à lui-même ? La propriété essentielle d’auto-reproduction qui se définit comme suit :
c est dite être auto-reproductive s’il existe une translation d telle que c construit cd
(la configuration c translatée de d).
Nous sommes désormais équipés pour distinguer l’auto-reproduction triviale de l’auto-reproduction non-triviale, selon la définition de von Neumann[28]. Nous dirons ainsi qu’une configuration c réalise la condition d’auto-reproduction non triviale si c est auto-reproductive et si c est un calculateur-constructeur universel. Nous verrons dans le chapitre III.2 que la distinction entre auto-reproduction triviale et non-triviale est fondamentale, et conduit à s’interroger sur la définition même de la vie.
Ces définitions, héritées en partie du monde de la logique (notion de calculabilité universelle) sont le point de départ d’une réflexion que l’on peut qualifier de ‘technique’ et qui vise à la construction effective d’un ‘ordinateur’ dans le monde cellulaire et d’une machine auto-reproductrice. A ce jour, seuls trois types d’automates auto-reproducteurs non triviaux (au sens défini précédemment) ont pu être effectivement construit dans un espace cellulaire bidimensionnel : il s’agit de l’automate de von Neumann, celui de Codd et de Life. Dans les deux premiers cas, l’espace cellulaire a été construit dans le but spécifique d’accueillir une configuration auto-reproductrice (non triviale) ; dans le cas de Life, il a fallu près de douze ans de recherches (1970-1982) pour parvenir à exhiber une telle configuration. La propriété de calculabilité-constructibilité universelle est donc un joyau rare dans le monde des automates cellulaires et la preuve de l’existence de cette propriété pour un automate donné reste le fruit d’un travail de longue haleine.