The complexity of reversible cellular automata

https://doi.org/10.1016/j.tcs.2004.06.011Get rights and content
Under an Elsevier user license
open archive

Abstract

We study the orbits of reversible one-dimensional cellular automata. It is shown that the Turing degree structure of the orbits of these automata is the same as for general cellular automata. In particular there are reversible cellular automata whose orbits have arbitrary recursively enumerable degree.

Keywords

Cellular automata
Intermediate degrees

Cited by (0)