Cet article, écrit conjointement avec Enrico Formenti et Bruno Durand, présente une approche nouvelle de la classification des automates cellulaires (AC) fondée sur la complexité de Kolmogorov. Nous construisons un paramètre κ qui est basé seulement sur la table de transition des AC et mesure le « caractère aléatoire » des évolutions. κ est meilleur, dans un certain sens, que n’importe quel autre paramètre calculable défini uniquement par la table de transition des AC. Nous avons aussi examiné les relations entre l’approche classique (topologique) et la notre. Notre paramètre a été aussi comparé au paramètre λ de Langton : le notre est plus fondé théoriquement, et s’accorde aussi avec des constatations expérimentales déjà publiées. Finalement, nous proposons aussi un protocole d’approximation de κ et d’expérimentation sur le comportement dynamique des AC.
Citer ce document
Cet article a été publié dans Theoretical Computer Science, revue très sérieuse d’informatique théorique.
Même s’il est marqué comme publié en mai 2001, la dernière révision est datée du 31 mars 1999. Parfois, c’est long, le processus éditorial...
@Article{ddf01,
author = {Jean-Christophe Dubacq and Bruno Durand and Enrico Formenti},
title = {{Kolmogorov} complexity and cellular automata classification},
journal = {Theoretical Computer Science},
year = {2001},
volume = {259},
number = {1--2},
pages = {271--285},
month = may
}
