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