Abstract of the article
The issue of testing invertibility of cellular automata has been often
discussed. The
computation universality of cellular automata has long been positively
resolved, and by showing that any cellular automaton could be simulated
by an invertible one having a superior dimension, Toffoli proved that
invertible cellular automaton of dimension d ≥2 were
computation-universal. Kenichi Morita proved that any invertible Turing Machine
could be simulated by a one-dimensional invertible cellular automaton,
which proved computation-universality of invertible
cellular automata. This article shows how to simulate any Turing
Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.
Quoting this publication
This article appeared in IJFCS, a journal that was rather Asia-centered at the time. The attached paper has been reformatted in the A4 format.
@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
}
