Approche évolutionniste de la recherche d'automates cellulaires universels

摘要

The famous problem of the frequency of universal cellular automata is related to emergence of computation in complex systems with simple local behaviour. It was asked by the first time by Wolfram : « How commun are computational universality and undecidability in cellular automata ». This paper includes evolutionary algorithms providing elements of answer to this problem. An evolutionary algorithm that finds automata accepting glider is described. Then we elaborated another algorithm that finds glider gun accepting by these automata. One of these automata is shown universal and our demonstration can be generalized to other automata that we discovered.%Le fameux problème de la fréquence des automates cellulaires universels est lié à l'émergence de la calculabilité dans les systèmes complexes avec des interactions locales. Il a été posé une première fois par Wolfram : « How commun are computational universality and undecidability in cellular automata ». Cet article décrit des algorithmes évolutionnaires donnant des éléments de réponse à cette problématique. Nous présentons un algorithme évolutionnaire découvrant des automates acceptant des planeurs puis un autre algorithme découvrant des canons à planeurs acceptés par ces automates. Un de ces automates est démontré universel et notre démonstration est généralisable aux autres automates découverts.