./.

Jean-Christophe Dubacq

Jean-Christophe Dubacq est maître de conférences au LIPN.

Accessoirement, de temps en temps, il fait:

Signaux pour automates cellulaires en dimension 2 ou plus

Dans cet article, co-écrit avec Véronique Terrier pour la conférence Latin 2002, nous regardons comment les automates cellulaires de dimension supérieure peuvent aider à tracer des signaux. Nous montrons l'existence d'un « trou » dans l'espace des signaux constructibles en dimension quelconque, Nous montrons à l'aide de deux automates cellulaires de dimension 2 qu'une dimension plus élevée permet de diminuer le nombre d'états nécessaires à certaines constructions.

lire la suite

Notion de préfixe dans la complexité de Kolmogorov et les modèles de calcul

La complexité de Kolmogorov donne une interprétation de la notion d'aléatoire pour les mots sur un alphabet fini. Ces notions ont conduit à l'explicitation de classes de fonctions calculables possédant des caractéristiques provenant de la théorie des codes: la classe des machines préfixes — machines dont le domaine est codé de façon préfixe, c'est-à-dire qu'un mot du domaine n'est jamais le préfixe d'un autre mot du domaine.

Outre la résolution du problème de l'aléatoire dans les mots infinis, cette classe de machine est stable vis-à-vis de la théorie de la calculabilité. On compare ici trois définitions distinctes de la notion de machine préfixe, mais remarquablement similaires. On étend ensuite les notions proposées aux codes comma free (sans facteurs). Certaines propriétés fondamentales sont alors non-vérifiées, comme l'existence d'une machine additivement optimale.
Enfin, on étudie la façon dont la notion de préfixe intervient dans la théorie de la calculabilité. On regarde en particulier les machines dont on limite le nombre de caractères (sans caractères blancs) ou encore la modélisation des modèles finis plongés dans des espaces de calcul infinis (ce qui est le cas de la machine de Turing, dotée d'un ruban infini).

lire la suite

Complexité de Kolmogorov et classification des automates cellulaires

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.

lire la suite

Introduction à la théorie algorithmique de l''information

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.

lire la suite

Simuler une machine de Turing par un automate cellulaire inversible

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.

lire la suite

Accès à d'autres pages: