Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426269 | Information and Computation | 2008 | 10 Pages |
We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. We study whether for a given real-time CA working on finite configurations with fixed boundary conditions there exists a reverse real-time CA with the same neighborhood. It is shown that real-time reversibility is undecidable, which contrasts the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the undecidability of emptiness, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freedom. First steps towards the exploration of the computational capacity are done and closure under Boolean operations is shown.