Registered: Oct 2003
Posts: 46

Here is a recent paper by Klaus Sutner:

Almost Periodic Configurations on Linear Cellular Automata.

http://www-2.cs.cmu.edu/~sutner/papers/backgrounds.pdf

Abstract: We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose orbits on backgrounds of all fixed sizes are decidable.


Comments:

It has nice discussion and proofs of facts about computability and complexity theory of CAs starting from simple seeds on repetitive backgrounds.

The simple initial conditions subject matter is very NKS relevant.

It includes discussion about ways of classifying evolutions, universality of simple rules like 110, and the Principle of Computational Equivalence.

Report this post to a moderator | IP: Logged