Abstract:
We give various characterizations for algorithmically random configurations on full
shift spaces, based on randomness tests. We show that all nonsurjective cellular au-
tomata destroy randomness and surjective cellular automata preserve randomness. Fur-
thermore all one-dimensional cellular automata preserve nonrandomness. The last three
assertions are also true if one replaces randomness by richness,|a form of pseudoran-
domness, which is compatible with computability, the last assertion even for an arbitrary
dimension.