ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 25/8-9 - 2006  - pp.1127-1155  - doi:10.3166/tsi.25.1127-1155
TITRE
Approche évolutionniste de la recherche d'automates cellulaires universels

RÉSUMÉ
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.


ABSTRACT
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.


AUTEUR(S)
Emmanuel SAPIN

MOTS-CLÉS
algorithmes évolutionnaires, automates cellulaires, universalité, planeurs, isotropie, canons à planeurs, jeu de la vie.

KEYWORDS
evolutionary algorithms, cellular automata, universality, gliders, isotropy, glider guns, game of life.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (583 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier