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. Ainsi, pour tout automate de dimension d ≥2, le problème est résolu. Toutefois le cas de la dimension 1 était encore à traiter. Kenichi Morita avait déjà résolu le problème en montrant qu’une machine de Turing réversible pouvait simuler une machine de Turing quelconque, et en faisant simuler ces machines réversibles par des automates cellulaires de dimension 1 de façon réversible.
Cet article présente une autre méthode, accessible à des étudiants de niveau M1 ou M2 pour prouver cela. En effet, partant de la simulation traditionnelle d’un automate cellulaire d’une machine de Turing et en utilisant un voisinage de taille 2 (ce qui peut ensuite se retransformer en un voisinage usuel {-1,0,1}) on peut projeter un historique de la simulation d’un côté sans que tout se mélange.
Citer ce document
L’article a été reformaté en A4 par rapport à l’original.
Cet article a été publié dans IJFCS, un journal (à l’époque) plutôt centré sur l’Asie (géographiquement).
@Article{dubacq95,
author = {Jean-Christophe Dubacq},
title = {How to simulate {Turing Machines} by invertible one-dimen\-sional cellular automata.},
journal = {Int. J. of Found. of Comp. Sci.},
year = 1995,
volume = 6,
number = 4,
pages = {395--402},
month = dec
}
