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.

Nous expliquons les bases de la théorie de la complexité de Kolmogorov ou théorie algorithmique de l'information. On analyse en particulier les différences et les ressemblances entre la complexité de Kolmogorov et sa variante dite complexité préfixe. Ensuite, nous introduisons une définition d'un mot aléatoire (finie ou infinie), celle de Per Martin-Löf et montrons qu'elle est équivalente à la notion d'incompressibilité définie via la complexité de Kolmogorov.

Il est indécidable de savoir si un automate cellulaire est inversible. L'universalité des automates cellulaires inversibles a été résolue par Toffoli qui a montré qu'un automate cellulaire quelconque peut-être simulé par un automate cellulaire de dimension juste supérieure. Cet article présente une méthode pour prouver le même théorème en dimension 1, accessible à des étudiants de niveau M1 ou M2 pour prouver cela.

Les automates cellulaires ont des propriétés très différentes selon qu'ils soient en dimension 1 ou 2 d'un point de vue de la calculabilité. Après avoir défini une notion de signal, on essaye ici d'analyser la puissance de calcul intrinsèque des automates cellulaires en une ou deux dimensions d'après la forme des signaux qu'il est possible de générer.

J'ai effectué des stages en laboratoire en licence (1993) et en maîtrise (1994) de l'École normale supérieure de Lyon respectivement au LIP et à l'IIT Madras (quand Chennai / சென்னை s'appelait encore Madras).