Long-range correlations in chaotic cellular automata (Q2277681)

A survey of numerical experiments is presented on relations between simulated cellular automata, probabilistic finite automata, and computation chains based on generalized Turing machines. Markov chains and computation chains with special grammars are used as approximations, mainly as a tool permitting to diminish computer time compared to that needed in direct simulations. A superficial resemblance to chaotic states of low-dimensional dynamic systems is noted in some graphical displays. The existence of long-range correlations is attributed to local irreversibility, i.e. to the property that more than one non-retraceable transient leads to a particular, apparently stationary state.