Surjectivity of nondeterministic parallel maps induced bynondeterministic cellular automata

摘要

For and d≥2, it is recursively unsolvable if the global mapping for a d-dimensionalnondeterministic cellular automaton is surjective. It is also unsolvable when the global mapping is restricted to the set of configurations with finite support.