{"id":"9b42dfe2-d0a9-4b0a-a3ad-244ae2182f80","arxiv_id":"1908.06751","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"The computational complexity of freezing, bounded-change, and convergent cellular automata depends on dimension and problem, with new decidability and computability separations.","lead":"This mathematics paper maps out how powerful three restricted types of cellular automata are as computers, depending on the dimension of the grid and the specific question asked. It shows surprising differences, such as a 1D convergent automaton being able to compute uncomputable limit configurations, while a 1D bounded-change one cannot.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9 rests on an unfinished local rule: the §5.2 validity checks and \"unique global head\" invariant are not shown to be enforceable by a finite-radius CA, so the bounded-change/convergent separation is not yet fully supported.","rationale":"The reader correctly identified the high-level specification of the Theorem 9 CA as the weak point. My stress test sharpens that concern: it is not merely that the transition table is omitted, but that some of the invariants the convergence proof relies on (unique global head, single block of 1s per belt component) are nonlocal and are asserted to be maintained by 'validity checks' without an argument that a finite-radius rule can enforce them while still converging on all configurations. The paper's own footnote about Preparingx degeneracy acknowledges an unresolved edge case. This does not show Theorem 9 is false; the construction is plausible and the surrounding results have detailed proofs. However, the flagship separation should not be graded at high confidence until the missing local rule and the validity-preservation/convergence induction are supplied. Hence I would change the verdict from ACCEPT to CONDITIONAL: accept subject to completing and verifying the Theorem 9 construction.","tokens_in":29850,"tokens_out":8656,"duration_ms":104874,"concrete_test":"Write out the complete finite-radius local transition table for the §5.2 construction, including all validity-check and error-generating rules. Then simulate the Theorem 9 initial configuration and, separately, an adversarial configuration containing two SH states separated by a block of L's. If the adversarial orbit produces no e yet fails to converge, the uniqueness assumption behind Lemmas 5-6 is false; if no complete local table can be produced without contradicting the stated mechanisms, Theorem 9 lacks a verified witness.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central separation in Theorem 9 is proved by a construction described only at mechanism level in §5.2: a global head, a conveyor-belt addressing component with zigzags, and a list of validity checks asserted to generate the spreading error state e. No complete local transition function is given. Two of the purported invariants are nonlocal: uniqueness of the global-head state SH and the property that each connected component of the virtual belt carries a single block of 1s. A finite-radius CA can enforce such properties only by local propagation plus an induction showing that every violating configuration either self-corrects or produces e; that induction is not supplied. In particular, the listed forbidden patterns (LR, RL, RSH, SHL, SHSH) do not prevent two SH states separated by a run of L's, so the uniqueness assumption used in Lemmas 5 and 6 is not shown to be preserved. If such a configuration persists without e, those convergence proofs have a gap. The paper itself concedes a related degeneracy in the Preparingx phase and says it can be avoided by sufficient spacing between zigzags, again without proof. Because Theorem 9 is the only source of the claimed 1D bounded-change-versus-convergent computability separation, this missing implementation is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies cellular automata in three increasingly general classes: freezing CA, bounded-change CA, and convergent CA. It develops a hierarchy of results across three benchmark problems: short-term prediction (PRED), long-term cylinder reachability (CYREACH), and the computability of limit fixed points from computable initial configurations. The central claims are: freezing and bounded-change CA have the same overall computational complexity in most settings; nilpotency is decidable in dimension 1 for all three classes but undecidable for freezing CA in higher dimensions; and in dimension 1 the computability of F^omega(c) separates bounded-change CA (always computable, Theorem 8) from convergent CA (uncomputable for a particular F and computable c, Theorem 9). The paper also contains a detailed Minsky-machine encoding into 1D freezing CA, communication-complexity bounds, and applications to self-assembly. Most proofs are given in full, with a notable exception in the construction of Theorem 9, which is described through high-level mechanisms rather than a complete local transition rule.","tokens_in":30151,"tokens_out":6943,"duration_ms":79413,"significance":"If the results hold, the paper makes a substantial contribution to the theory of cellular automata: the computability separation of limit configurations is surprising, the nilpotency decidability result for 1D convergent CA is elegant, and the Minsky-machine encoding is a useful reusable construction. The paper is also genuinely careful in many places: Lemma 1 and the shrinking-zone construction are fully worked out, the reductions for PRED and CYREACH are explicit, and Theorem 8's argument is a thoughtful use of bounded-change structure. The use of external benchmarks (Kari, Salo, Berger, aTAM results) is appropriate. The main obstacle to accepting the paper as is is the unfinished local specification of the convergent CA in Theorem 9; this is load-bearing for the paper's headline separation between bounded-change and convergent CA in dimension 1.","major_comments":[{"comment":"The CA F used in Theorem 9 is not fully specified. The text describes intended mechanisms (unique global head, conveyor belt, zigzag counters, validity checks) and asserts that violations produce the error state e, but it does not give a complete local transition function. In particular, the uniqueness of the global-head state SH is a nonlocal invariant: the forbidden patterns LR, RL, RSH, SHL and SHSH do not rule out two SH states separated by a run of L states. Lemmas 5 and 6 repeatedly reason about 'the' global head, so they implicitly rely on this uniqueness; the proof that every configuration violating it either self-corrects or generates e is not supplied. Since Theorem 9 is the only source of the claimed 1D bounded-change-versus-convergent computability separation, this missing implementation is load-bearing and must be completed.","section":"Section 5.2, Lemmas 5-6 and Theorem 9"},{"comment":"The paper explicitly concedes that the Preparingx phase can generate e when the head exits a zigzag and later enters a new one, and says this 'can easily be avoided by a sufficient spacing between zigzags.' No such spacing proof is given for the initial configuration of Theorem 9, which places exactly one simple-belt cell between consecutive zigzags. Moreover, convergence of F must hold for every configuration, not only for configurations with large spacing. The authors must either prove that the stated spacing of the chosen c suffices for the whole orbit, or modify the local rule so that all degenerate cases provably produce e; otherwise the convergence argument for F is incomplete.","section":"Section 5.2, footnote (v)"},{"comment":"The proof asserts without a formal argument that a zigzag of length k will be crossed at most k times and that the Return stage 'poses no problem.' This is used to guarantee that marking processes terminate and that the addressing component converges. A rigorous proof needs an invariant bounding the number of successful crossings of each zigzag by the marking head, valid for all configurations, together with a verification that the Turing program's scheduling in the chosen initial configuration respects that invariant for every mark that is ever launched. Without this, the convergence of the addressing component in Lemma 6, and hence the convergence of F, is not established.","section":"Theorem 9 proof, final paragraph"}],"minor_comments":[{"comment":"The abstract contains a typo: 'cristal growth' should be 'crystal growth.'","section":"Abstract"},{"comment":"The stated running time O(n|V|) for deciding whether a CA is freezing appears to be a typo: scanning the transition table of a CA with n states and neighborhood V requires time proportional to n^{|V|}, not n|V|.","section":"Fact 1"},{"comment":"The text refers to 'Figure 4.3' but the figure is actually numbered 'Fig. 2'; the cross-reference should be corrected.","section":"Section 4.3"},{"comment":"The theorem statement says 'any bound-change CA'; this should be 'bounded-change CA' for consistency.","section":"Theorem 3"},{"comment":"The definition of CYREACHF would be clearer if it stated explicitly that both cylinders [u] and [v] are centered at the origin, since cylinders were defined in Section 1 only for bounded configurations centered on cell 0.","section":"Definition 5"}],"recommendation":"major_revision","confidential_remarks":"The paper's main theorems other than Theorem 9 appear sound and well-supported, and the exposition is generally careful. The missing local transition rule and invariant proofs for the convergent CA in Section 5.2 are the only substantive obstruction; however, since Theorem 9 is the headline separation result, this is not a minor issue. I would be willing to accept after the authors supply a complete local specification (or a different proof) together with the missing induction showing that every violation of the stated invariants produces e, and after the 'sufficient spacing' claim in footnote (v) is either proved or removed by modifying the construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core of it is good: it gives a clean complexity landscape for freezing, bounded-change, and convergent CA, and most of the proofs are complete and careful. Second, the one genuinely surprising separation—1D bounded-change has computable limits, 1D convergent can have uncomputable limits—is proved with a construction that is not fully specified, and that gap is load-bearing.\n\nWhat's new and worth taking seriously: the systematic study of convergent CA is long overdue, and the results organize a lot of scattered phenomena. The decidability of nilpotency in 1D for all three classes (Theorem 2) is a nice, clean consequence of Proposition 1 plus the De Bruijn graph argument. The Minsky machine encoding in Section 4.3 is detailed and supports both the undecidability of CYREACH and the k-change undecidability. The communication complexity separation (Theorem 3 vs Proposition 8) is also solid and plays well with the existing literature. The paper is honest about its debts: Kari, Salo, Berger, aTAM results, and the authors' own earlier work are cited and used appropriately.\n\nThe soft spot is Theorem 9. The reader's report calls it a presentation gap; the stress-test goes further, and I think correctly. The convergent CA in Section 5.2 is described by intended mechanisms—global head, conveyor belt, zigzag counters—plus a list of validity checks. But there is no complete local transition function, and two of the invariants used in Lemmas 5 and 6 are nonlocal: uniqueness of the SH head state and the \"single block of 1s per belt component\" property. The listed forbidden patterns do not obviously prevent two SH states separated by a run of L's, and the paper itself concedes a related degeneracy in the Preparing phase (the \"sufficient spacing between zigzags\" remark in Section 5.2) without proof. The convergence proofs in Lemmas 5 and 6 rely on those invariants. So the separation is not fully established as written.\n\nThat said, the construction is plausible. The missing piece is an implementation-level argument: show that a finite-radius CA can enforce these invariants via local propagation, or explicitly handle the violating configurations. This is a repair, not a refutation. The rest of the paper stands.\n\nWho is this for? Anyone working on CA complexity, freezing/sandpile-type dynamics, or the computability of limits in symbolic dynamics. It deserves a serious referee—but the referee should be asked to focus on Section 5.2 and demand either a complete transition table or a rigorous lemma that the listed checks are enforceable. I would not desk-reject, but I would not accept without revision. My recommendation: send it to review, and flag Theorem 9 as the must-fix point.","headline":"A strong, mostly rigorous complexity-landscape paper whose one load-bearing separation (Theorem 9) rests on a construction described only at mechanism level, not a checkable local rule.","tokens_in":30657,"tokens_out":890,"would_cite":true,"duration_ms":12243,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["37B15","68Q80","03D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A one-dimensional convergent cellular automaton can have an uncomputable limit configuration, while bounded-change automata in 1D always have computable limits.","keywords":["freezing cellular automata","bounded-change cellular automata","convergent cellular automata","limit configuration computability","nilpotency decision problem","communication complexity","prediction problem","cylinder reachability"],"falsifier":"Implement the Section 5.2 automaton as the paper describes it, with the intended validity checks, and run it on a Turing machine known to halt quickly. If the marking process fails to place a 1 at the matching zigzag, or if a zigzag counter is decremented too many times and produces the error state $e$ during a legitimate run, the convergence invariant is violated and Theorem 9's construction is broken. Conversely, if such a finite transition table exists and keeps all stated invariants, the separation is established; the concrete hinge is whether the checks fire exactly on the forbidden patterns and never elsewhere.","tokens_in":29671,"feed_emoji":"🌀","tokens_out":9391,"duration_ms":85951,"temperature":0.7,"pith_summary":"This paper asks how three convergence-like restrictions on cellular automata change what the automata can compute and which of their properties are decidable. The restrictions are: freezing rules, where a cell's state can only decrease along a fixed order; bounded-change rules, where each cell changes state at most a fixed number of times; and convergent rules, where every orbit reaches a fixed point. The central claim is that these three classes form a strict hierarchy whose computational power depends on the dimension and on the problem considered. In particular, in one dimension bounded-change rules always give computable limits from computable initial configurations, while some merely convergent rules give uncomputable limits; and in higher dimensions even freezing rules can simulate hard computations. The paper also proves that nilpotency is decidable in dimension 1 for all three classes but undecidable for freezing rules in dimension 2 and above.","feed_headline":"Convergent automata can output uncomputable limits","feed_subtitle":"In 1D, merely convergent rules can compute a limit no Turing machine can; bounded-change rules cannot.","key_machinery":"The paper's central objects are the three classes themselves—freezing, bounded-change, and convergent cellular automata—and the proofs run through two main construction techniques. For upper bounds, the load-bearing tool is the compact column representation of a space-time diagram: in a $k$-change automaton a column can be stored as a list of at most $k$ (state, duration) pairs, which yields a NLOGSPACE prediction algorithm and a communication protocol of cost $O(n^{d-1}\\log n)$ for bounded-change automata. For lower bounds, the shrinking-zone construction (Example 7) makes a global head sweep through a working zone, applying a given cellular automaton's rule synchronously and shrinking the zone at each bounce, while remaining convergent but not bounded-change; this gives P-complete prediction and undecidable reachability. Finally, the convergent automaton of Section 5.2 uses a global head, a conveyor-belt addressing layer with zigzag counters, and a marker layer, so that a marking snake of unary length reaches a matching zigzag only when the simulated Turing machine halts; the bounded zigzag counters keep every orbit convergent.","core_discovery":"The paper establishes a computational separation between bounded-change and convergent one-dimensional cellular automata, and between one- and higher-dimensional freezing automata. Theorem 8 shows that for every 1D bounded-change automaton $F$ and every computable configuration $c$, the limit configuration $F^\\omega(c)$ is computable; Theorem 9 shows that there exists a 1D convergent automaton and a computable configuration whose limit is uncomputable. The same construction techniques give P-complete short-term prediction and undecidable cylinder reachability for convergent automata in 1D, while bounded-change prediction lies in NLOGSPACE. In dimension 2, the paper exhibits freezing automata whose reachability problem is undecidable and whose limit configurations, even from finite initial data, can have characteristic sets that are neither recursively enumerable nor co-recursively enumerable. Nilpotency is decidable in polynomial time for 1D convergent automata and undecidable for freezing automata in higher dimensions.","pith_inferences":["The paper's Section 5.2 construction is described by intended mechanisms rather than a complete local transition table; if the encoding cannot be carried out without accidental error-state generation, the uncomputable-limit separation in Theorem 9 would not go through. Supplying a fully explicit table is the immediate technical test.","The same global-head and zigzag-counter mechanism is a candidate template for realizing any $\\Delta_2^0$ limit set with a 1D convergent automaton; a full characterization of which limit sets are realizable would place the class precisely in the arithmetical hierarchy.","Because the bounded-change limit-computability proof uses only radius and per-cell change bounds, it should extend to any 1D network with bounded per-cell changes, not just cellular automata with translation-invariant rules.","The P-completeness and undecidability of reachability for 1D convergent automata suggests that the shrinking-zone simulation is a general embedding of arbitrary CA into convergent dynamics, so other undecidable CA properties are likely to transfer."],"forward_implications":["In 1D, bounded-change constraints guarantee that every computable initial configuration has a computable limit; any failure of computability in a limit must therefore come from unbounded-change convergent behavior.","A single convergent 1D automaton with P-complete prediction and undecidable reachability exists, so convergence alone does not tame the dynamics.","Under the standard complexity separation $\\mathrm{PTIME} \\neq \\mathrm{NLOGSPACE}$, 1D bounded-change prediction is strictly easier than convergent prediction.","Nilpotency is decidable for all three classes in 1D, so convergence plus one dimension gives a decidable property that is undecidable in higher dimensions even for freezing rules.","In 2D, freezing automata can realize limit configurations whose marker sets are neither r.e. nor co-r.e. from finite initial data, escaping the first level of the arithmetical hierarchy."],"supporting_citations":[{"why":"Defines freezing cellular automata and the 1D encoding scheme whose full proofs this paper supplies; the starting point for class definitions and Minsky-machine simulation.","marker":"[14]"},{"why":"Proves the nilpotency problem undecidable for 1D CA, the reduction source for undecidability of bounded-change/convergent membership and for nilpotency in 2D.","marker":"[22]"},{"why":"Introduces cylinder-reachability universality and the hard instance used to define the benchmark reachability problem.","marker":"[10]"},{"why":"Introduces bounded-change CA as language recognizers, the basis for the NLOGSPACE prediction result and the earlier complexity view.","marker":"[43]"},{"why":"Provides the directed aTAM construction whose unique terminal assemblies encode arbitrary recursively enumerable sets, used to build 2D freezing CA with limit sets outside r.e. and co-r.e.","marker":"[28]"},{"why":"Supplies Minsky's counter machines, simulated by the 1D freezing construction to prove undecidable reachability and undecidable change-bound.","marker":"[30]"},{"why":"Gives Berger's undecidability of the tiling problem, used for undecidability of nilpotency for freezing CA in dimension 2 and above.","marker":"[5]"},{"why":"Shows P-completeness of rule 110, used to obtain P-complete prediction for the constructed convergent and 2D freezing automata.","marker":"[34]"},{"why":"Defines the communication complexity model used to measure prediction communication and to prove the bounded-change upper and convergent lower bounds.","marker":"[45]"}],"fun_headline_variants":["1D convergent rules compute uncomputable limits","Bounded-change vs convergent: 1D limit computability split","Nilpotency decidable in 1D, not in 2D for freezing automata","Freezing automata: dimension flips nilpotency decidability","Convergent automata can yield uncomputable limits in 1D"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction behind Theorem 9 depends on being able to turn the described high-level mechanisms (a single global head, conveyor-belt addressing, zigzag counters) into a finite-radius local transition rule without generating the error state in legitimate configurations; if no such rule exists, the uncomputability result is not established.","fun_headline_variants_meta":{"raw":{"variants":["1D convergent rules compute uncomputable limits","Bounded-change vs convergent: 1D limit computability split","Nilpotency decidable in 1D, not in 2D for freezing automata","Freezing automata: dimension flips nilpotency decidability","Convergent automata can yield uncomputable limits in 1D"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000837,"raw_usage":{"total_tokens":3709,"prompt_tokens":1062,"completion_tokens":2647,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":2552}},"tokens_in":678,"tokens_out":2647,"duration_ms":19415,"temperature":1.0,"reasoning_tokens":2552,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:36:47.028374+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the Section 5.2 automaton as the paper describes it, with the intended validity checks, and run it on a Turing machine known to halt quickly. If the marking process fails to place a 1 at the matching zigzag, or if a zigzag counter is decremented too many times and produces the error state $e$ during a legitimate run, the convergence invariant is violated and Theorem 9's construction is broken. Conversely, if such a finite transition table exists and keeps all stated invariants, the separation is established; the concrete hinge is whether the checks fire exactly on the forbidden patterns and never elsewhere.","supporting_citations":[{"cited_title":"In: Kari, J., Törmä, I., Szabados, M","cited_arxiv_id":null,"evidence_quote":"Defines freezing cellular automata and the 1D encoding scheme whose full proofs this paper supplies; the starting point for class definitions and Minsky-machine simulation."},{"cited_title":"SIAM Journal on Com- puting 21, 571–586 (1992)","cited_arxiv_id":null,"evidence_quote":"Proves the nilpotency problem undecidable for 1D CA, the reduction source for undecidability of bounded-change/convergent membership and for nilpotency in 2D."},{"cited_title":"Fundamenta Informaticae 74(4), 463–490 (2006), http://content.iospress.com/ articles/fundamenta-informaticae/fi74-4-06","cited_arxiv_id":null,"evidence_quote":"Introduces cylinder-reachability universality and the hard instance used to define the benchmark reachability problem."},{"cited_title":"In: Knödel, W., Schneider, H","cited_arxiv_id":null,"evidence_quote":"Introduces bounded-change CA as language recognizers, the basis for the NLOGSPACE prediction result and the earlier complexity view."},{"cited_title":"Theory of Computing Systems 48(3), 617–647 (2011), https://doi.org/10","cited_arxiv_id":null,"evidence_quote":"Provides the directed aTAM construction whose unique terminal assemblies encode arbitrary recursively enumerable sets, used to build 2D freezing CA with limit sets outside r.e. and co-r.e."},{"cited_title":"Prentice Hall, Englewoods Cliffs (1967)","cited_arxiv_id":null,"evidence_quote":"Supplies Minsky's counter machines, simulated by the 1D freezing construction to prove undecidable reachability and undecidable change-bound."},{"cited_title":"Memoirs of the American Mathematical Society 66 (1966)","cited_arxiv_id":null,"evidence_quote":"Gives Berger's undecidability of the tiling problem, used for undecidability of nilpotency for freezing CA in dimension 2 and above."},{"cited_title":"In: ICALP 2006","cited_arxiv_id":null,"evidence_quote":"Shows P-completeness of rule 110, used to obtain P-complete prediction for the constructed convergent and 2D freezing automata."},{"cited_title":"In: STOC 1979","cited_arxiv_id":null,"evidence_quote":"Defines the communication complexity model used to measure prediction communication and to prove the bounded-change upper and convergent lower bounds."}],"review_version":1}