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é dun 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 dautres 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 quune machine de Turing, la différence fondamentale étant que toutes les cellules de lespace 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 dune 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 lon lui donne une description complète dune 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 lunivers des AC, il nest 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 dobstacle majeur mais conduit, si lon sy prend de façon « brutale », à utiliser un grand nombre détats différents, limitant par-là lintérêt dutiliser des AC comme modèle. On comprend dès lors la difficulté à prouver de façon constructive lexistence dun calculateur universel qui nutilise quun 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 lacte de naissance dun 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 lensemble des bandes qui contiennent seulement un nombre fini de symboles non vides et W lensemble des symboles utilisés dans T. Une fonction partielle ? est dite calculable par machine de Turing, sil existe une machine de Turing munie de lalphabet W qui calcule ?.
La première étape dans la démonstration de léquivalence M.T / A.C consiste à associer lespace des bandes T à lespace cellulaire Z muni de configurations totalement passives. Nous retrouvons là le fait que les cellules des configurations totalement passives sont de simples supports de linformation.
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 darrê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) à laide du tableau suivant :
Machine de Turing |
Automate cellulaire |
état de la machine et de la bande | cellules dans un certain état |
état darrêt qui marque la fin du calcul | activation dune 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 na 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 , quon notera s= sd en abrégé.
On dira dun espace cellulaire quil 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. Sil 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 cur dune épistémologie des automates cellulaires.
Nous pouvons désormais utiliser la spécificité des automates cellulaires pour enrichir notre capital de définitions : il sagit de définir la propriété de constructibilité. Une configuration donnée peut en effet évoluer en conduisant à la création dautres configurations, lesquelles configurations vont à leur tour pouvoir évoluer librement dans lespace cellulaire. Si on fait lanalogie « 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 dinformation à c.
En clair, la configuration construite (lobjet construit) doit être construite à lextérieur de la configuration initiale(le constructeur). Par ailleurs, une fois terminée létape de construction de lobjet construit, il ne doit y avoir aucune interaction entre le constructeur c et lobjet 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 dauto-reproduction triviale. Ceci correspond bien à lidée que nous nous faisons dune machine-outil : celle-ci conduit à lélaboration dautres 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 quun 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 sil 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 lespace accueillant cu est dit posséder la propriété de constructibilité universelle[27].
Nous approchons du problème central de lauto-reproduction, tel que von Neumann la 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 dauto-reproduction qui se définit comme suit :
c est dite être auto-reproductive sil existe une translation d telle que c construit cd
(la configuration c translatée de d).
Nous sommes désormais équipés pour distinguer lauto-reproduction triviale de lauto-reproduction non-triviale, selon la définition de von Neumann[28]. Nous dirons ainsi quune configuration c réalise la condition dauto-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 à sinterroger 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 dune réflexion que lon peut qualifier de technique et qui vise à la construction effective dun ordinateur dans le monde cellulaire et dune machine auto-reproductrice. A ce jour, seuls trois types dautomates auto-reproducteurs non triviaux (au sens défini précédemment) ont pu être effectivement construit dans un espace cellulaire bidimensionnel : il sagit de lautomate de von Neumann, celui de Codd et de Life. Dans les deux premiers cas, lespace cellulaire a été construit dans le but spécifique daccueillir 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 lexistence de cette propriété pour un automate donné reste le fruit dun travail de longue haleine.