Résumé
It is well known that one-dimensional cellular automata working on the usual neighborhood are Turing complete, and many acceleration theorems are known. However very little is known about the other neighborhoods. In this article, we prove that every one-dimensional neighborhood that is sufficient to recognize every Turing language is equivalent (in terms of real-time recognition) either to the usual neighborhood {–1,0,1} or to the one-way neighborhood {0,1}.