Some Pointwise and Decidable Properties of Non-Uniform Cellular Automata

The uploaded paper proves decidability for (i) nilpotency, (ii) periodicity, (iii) eventual periodicity, (iv) Cayley–Hamilton, (v) injectivity, and (vi) post-surjectivity for asymptotically constant linear NUCA over Z^d with finite alphabet (Theorem A) and gives explicit constructive reductions via induced local maps plus a finite-dimensional endomorphism ϕ, together with a separate effective procedure for injectivity and a duality reduction for post-surjectivity . The candidate solution largely mirrors this scheme, but it makes a critical logical misstep for (i): after finding N with τ∞^N=0, it claims τ is nilpotent iff the induced restriction D_N on a finite window is the zero map. The paper instead shows one must form a finite endomorphism ϕ:W→W and test whether ϕ is nilpotent; requiring D_N=0 is too strong and would incorrectly reject NUCA that become zero only after further iterations (the paper’s algorithm checks ϕ^dimW=0 instead) . For (ii)–(iii), the paper again reduces to a finite endomorphism ϕ and checks its (eventual) periodicity, not merely identity of a single iterate on the window; the candidate’s description is imprecise here, although directionally aligned . The equivalence CH ⇔ EP in the finite-alphabet linear case follows from the paper’s Theorems 6.3 and 6.4 plus the trivial converse, matching the candidate’s intention . Injectivity is handled by an explicit effective construction (Theorem 9.5), and post-surjectivity is reduced to injectivity of the effectively computable dual NUCA in the proof of Theorem A, both consistent with the candidate’s outline .