Pith. sign in

REVIEW 3 major objections 5 minor 46 references

Freezing, Bounded-Change and Convergent Cellular Automata

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A one-dimensional convergent cellular automaton can have an uncomputable limit configuration, while bounded-change automata in 1D always have computable limits.

desk verdict 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. read the letter →

arxiv 1908.06751 v4 pith:CEPIOTB7 submitted 2019-08-19 cs.DM cs.CCnlin.CG

Nicolas Ollinger (LIFO) , Guillaume Theyssier (I2M) This is my paper · ORCID
classification cs.DMcs.CCnlin.CG MSC 37B1568Q8003D15
keywords freezingcellularautomatabounded-changeconvergentlimitconfigurationcomputabilitynilpotencydecisionproblemcommunicationcomplexitypredictioncylinderreachability
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 5.2, Lemmas 5-6 and Theorem 9] 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.
  2. [Section 5.2, footnote (v)] 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.
  3. [Theorem 9 proof, final paragraph] 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.
minor comments (5)
  1. [Abstract] The abstract contains a typo: 'cristal growth' should be 'crystal growth.'
  2. [Fact 1] 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|.
  3. [Section 4.3] The text refers to 'Figure 4.3' but the figure is actually numbered 'Fig. 2'; the cross-reference should be corrected.
  4. [Theorem 3] The theorem statement says 'any bound-change CA'; this should be 'bounded-change CA' for consistency.
  5. [Definition 5] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's derivations are self-contained and externally benchmarked; self-citations are not load-bearing.

full rationale

The paper's derivation chain is self-contained and benchmarked against external results. The main constructions (Lemmas 1, 3, 4; Propositions 4-8) are proven from explicitly given local transition rules and reductions from independent undecidable problems (Kari, Berger, Minsky). The authors' prior work [14] is explicitly superseded: the paper says it gives 'complete detailed proofs of all results of [14]', so no load-bearing claim rests on an unverified self-citation. Theorem 8 is proven by a self-contained space-time argument, and Theorem 9 introduces a new construction with stated invariants; the skeptic's concern that the global-head uniqueness invariant is not shown to be enforceable by a finite-radius local rule is a legitimate correctness/completeness gap, not a circularity, because the theorem does not define its conclusion into its hypotheses nor fit a parameter and then predict it. External citations (Salo's asymptotic-nilpotency theorem, the aTAM construction [28]) are used as independent lemmas with stated assumptions that do not include the target results. No equation or claimed prediction reduces by construction to an input, and no fitted data are renamed as predictions.

Assumptions & free parameters 1 free parameters · 7 assumptions · 3 invented entities

The paper introduces no fitted parameters; the only hand-chosen constant is K in the Minsky construction, which is arbitrary and not data-dependent. The central claims rest on standard theorems from the literature, which are cited. The main invented entities are explicit CA constructions whose properties are proved; the only partially formalized one is the global head CA of Theorem 9.

free parameters (1)
  • K = 3k + 3 = 3k + 3
    Chosen as a sufficiently large bound in the Minsky machine construction (Section 4.3, Theorem 6) to ensure the maximal state-change chain i0 to iK is unique. Not fitted to data; any sufficiently large constant would work.
assumptions (7)
  • standard math Curtis-Lyndon-Hedlund theorem
    Used throughout to define cellular automata by local transition rules and to justify the finite-radius formulation.
  • domain assumption Kari's theorem that nilpotency of 1D CA is undecidable
    Used as the base problem in the reductions of Theorem 1 and for the higher-dimensional undecidability in Theorem 2.
  • domain assumption Salo's theorem: asymptotically q0-nilpotent CA is nilpotent
    Load-bearing in Proposition 1, which is the key step for the polynomial-time decidability of nilpotency in 1D convergent CA (Theorem 2).
  • domain assumption Berger's undecidability of the domino problem
    Used in the proof of Theorem 2 to show undecidability of nilpotency for 2D freezing CA via Wang tilings.
  • domain assumption Existence of rule 110 with P-complete PRED and of a CA with undecidable CYREACH
    Used as building blocks in Propositions 4 and 5 to produce hard examples for freezing and convergent CA.
  • domain assumption Lathrop, Lutz, Patitz, Summers theorem on directed aTAM systems
    Used in Corollary 1 to encode arbitrary recursively enumerable sets into limit configurations of 2D freezing CA.
  • domain assumption Balance theorem for surjective cellular automata
    Used in Proposition 3 to show that a surjective convergent CA must be the identity.
invented entities (3)
  • Shrinking zone CA Z_F (Example 7)
    purpose: Simulate any 1D CA while being convergent but not bounded-change; used in Proposition 5 and Theorem 1.
    Fully specified construction with an explicit transition rule; its convergence and simulation properties are proved in Lemma 1. Not an unexplained postulate.
  • Convergent CA F of Theorem 9 (global head construction)
    purpose: Produce uncomputable limit configurations from computable initial configurations in 1D.
    Described through validity checks and intended head behaviors rather than a complete transition table; the proof assumes the described mechanisms can be realized as a finite-radius CA.
  • Minsky machine encoding F_M (Section 4.3)
    purpose: Simulate any k-counter Minsky machine by a 1D freezing CA; used for Theorem 5 and Theorem 6.
    Fully specified transition rule f_M is given, and correctness is proved in Lemmas 3 and 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Freezing, Bounded-Change and Convergent Cellular Automata." pith.science (2026). https://pith.science/paper/CEPIOTB7

@misc{pith2026190806751,
  author       = {Pith},
  title        = {Pith review of: Freezing, Bounded-Change and Convergent Cellular Automata},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CEPIOTB7}},
  note         = {Machine review of arXiv:1908.06751}
}
read the original abstract

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.

Figures

Figures reproduced from arXiv: 1908.06751 by the authors.

Figure 1
Figure 1. Some examples of freezing CA studied in the literature: (a) configuration of Ulam’s rule from Example 1 after some steps starting from a single 1 in a sea of 0s; (b) spatio-temporal representation of the standard bootstrap percolation model (Example 2) where shades of gray represent time at which a cell turned to 1 (the whiter the sooner); (c) a configuration of a model of forest fire as in Example 4 (fire is repres… view at source ↗
Figure 2
Figure 2. Example of space-time diagram of FM (on the right) simulating the Minsky machine M started on an empty counter (on the left). To simplify, we supposed K = 1 and any state (#α, δ) is represented as #α [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Conveyor belt and zigzags in the addressing component. (plus a fourth layer used as a passage counter for the zigzag). Each position in this virtual belt has a well-defined predecessor and successor as depicted in [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    Biophysics 36(2), 356–360 (1991)

    Alekseyevskaya, T., Malenkov, A.: Mathematical model of the initiation of near weekly fluctuations in tissue (cellular automata). Biophysics 36(2), 356–360 (1991)

    work page 1991

  2. [2]

    Physics Letters A 147(5-6), 297–300 (1990), https://doi.org/10.1016/0375-9601(90)90451-S Freezing, Bounded-Change and Convergent Cellular Automata 35

    Bak, P., Chen, K., Tang, C.: A forest-fire model and some thoughts on turbulence. Physics Letters A 147(5-6), 297–300 (1990), https://doi.org/10.1016/0375-9601(90)90451-S Freezing, Bounded-Change and Convergent Cellular Automata 35

    work page doi:10.1016/0375-9601(90)90451-s 1990

  3. [3]

    In: CiE 2018

    Becker, F., Maldonado, D., Ollinger, N., Theyssier, G.: Universality in freezing cellular automata. In: CiE 2018. Lecture Notes in Computer Science, vol. 10936, pp. 50–59. Springer (2018),https: //doi.org/10.1007/978-3-319-94418-0_5

    work page doi:10.1007/978-3-319-94418-0_5 2018

  4. [4]

    It's a Tough Nanoworld: in Tile Assembly, Cooperation is not (strictly) more Powerful than Competition

    Becker, F., Meunier, P.: It’s a tough nanoworld: in tile assembly, cooperation is not (strictly) more powerful than competition. CoRR abs/1502.05558 (2015), http://arxiv.org/abs/1502. 05558

    work page Pith review arXiv 2015

  5. [5]

    Memoirs of the American Mathematical Society 66 (1966)

    Berger, R.: The undecidability of the domino problem. Memoirs of the American Mathematical Society 66 (1966)

    work page 1966

  6. [6]

    Discrete Mathematics & Theoretical Computer Science 15(3), 41–60 (2013), http://dmtcs

    Capobianco, S., Guillon, P., Kari, J.: Surjective cellular automata far from the garden of eden. Discrete Mathematics & Theoretical Computer Science 15(3), 41–60 (2013), http://dmtcs. episciences.org/618

    work page 2013

  7. [7]

    In: AUTOMATA 2018

    Carton, O., Guillon, B., Reiter, F.: Counter machines and distributed automata - A story about exchanging space and time. In: AUTOMATA 2018. Lecture Notes in Computer Science, vol. 10875, pp. 13–28. Springer (2018), https://doi.org/10.1007/978-3-319-92675-9_2

    work page doi:10.1007/978-3-319-92675-9_2 2018

  8. [8]

    Cambridge University Press (2005)

    Chopard, B., Droz, M.: Cellular Automata Modeling of Physical Systems. Cambridge University Press (2005)

    work page 2005

Show all 46 references
  1. [9]

    In: ICALP 2011

    Delacourt, M.: Rice’s theorem forµ-limit sets of cellular automata. In: ICALP 2011. Lecture Notes in Computer Science, vol. 6756, pp. 89–100. Springer (2011), https://doi.org/10.1007/ 978-3-642-22012-8_6

    2011

  2. [10]

    Fundamenta Informaticae 74(4), 463–490 (2006), http://content.iospress.com/ articles/fundamenta-informaticae/fi74-4-06

    Delvenne, J., K˚ urka, P., Blondel, V .D.: Decidability and universality in symbolic dynamical sys- tems. Fundamenta Informaticae 74(4), 463–490 (2006), http://content.iospress.com/ articles/fundamenta-informaticae/fi74-4-06

    2006

  3. [11]

    Theoretical Computer Science 412(1-2), 145–158 (2011), https://doi.org/10.1016/j.tcs.2010

    Doty, D., Patitz, M.J., Summers, S.M.: Limitations of self-assembly at temperature 1. Theoretical Computer Science 412(1-2), 145–158 (2011), https://doi.org/10.1016/j.tcs.2010. 08.023

    2011 doi

  4. [12]

    Physica A: Statistical Mechanics and its Applications 267(3–4), 471–486 (1999)

    Fuentes, M., Kuperman, M.: Cellular automata and epidemiological models with spatial depen- dence. Physica A: Statistical Mechanics and its Applications 267(3–4), 471–486 (1999)

    1999

  5. [13]

    Journal of Computer and System Sciences 78(4), 1115–1126 (2012), https://doi.org/10.1016/j.jcss.2012

    Gajardo, A., Kari, J., Moreira, A.: On time-symmetry in cellular automata. Journal of Computer and System Sciences 78(4), 1115–1126 (2012), https://doi.org/10.1016/j.jcss.2012. 01.006

    2012 doi

  6. [14]

    In: Kari, J., Törmä, I., Szabados, M

    Goles, E., Ollinger, N., Theyssier, G.: Introducing freezing cellular automata. In: Kari, J., Törmä, I., Szabados, M. (eds.) Exploratory Papers of AUTOMATA 2015. TUCS Lecture Notes, vol. 24, pp. 65–73 (2015)

    2015

  7. [15]

    In: AUTOMATA 2017

    Goles, E., Maldonado, D., Montealegre, P., Ollinger, N.: On the computational complexity of the freezing non-strict majority automata. In: AUTOMATA 2017. Lecture Notes in Com- puter Science, vol. 10248, pp. 109–119. Springer (2017), https://doi.org/10.1007/ 978-3-319-58631-1_9...

    2017

  8. [16]

    Theoretical Computer Science 412(1-2), 2–21 (2011), https: //doi.org/10.1016/j.tcs.2010.10.005

    Goles Ch., E., Meunier, P., Rapaport, I., Theyssier, G.: Communication complexity and intrinsic universality in cellular automata. Theoretical Computer Science 412(1-2), 2–21 (2011), https: //doi.org/10.1016/j.tcs.2010.10.005

    2011 doi

  9. [17]

    Advances in Applied Mathematics 21(2), 241–304 (1998), https://doi.org/10.1006/ aama.1998.0599

    Gravner, J., Griffeath, D.: Cellular automaton growth on Z2: Theorems, examples, and problems. Advances in Applied Mathematics 21(2), 241–304 (1998), https://doi.org/10.1006/ aama.1998.0599

    1998

  10. [18]

    Complex Systems 10, 437–448 (1996)

    Griffeath, D., Moore, C.: Life without death is P-complete. Complex Systems 10, 437–448 (1996)

    1996

  11. [19]

    Guillon, P.: Automates cellulaires : dynamiques, simulations, traces. Ph.D. thesis, Université Paris Est (2008), http://www.theses.fr/2008PEST0215

    2008

  12. [20]

    Mathematical Systems Theory 3(4), 320–375 (1969)

    Hedlund, G.A.: Endomorphisms and Automorphisms of the Shift Dynamical Systems. Mathematical Systems Theory 3(4), 320–375 (1969)

    1969

  13. [21]

    Probability Theory and Related Fields 125(2), 195–224 (2003)

    Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probability Theory and Related Fields 125(2), 195–224 (2003)

    2003

  14. [22]

    SIAM Journal on Com- puting 21, 571–586 (1992)

    Kari, J.: The Nilpotency Problem of One-dimensional Cellular Automata. SIAM Journal on Com- puting 21, 571–586 (1992)

    1992

  15. [23]

    Theoretical Computer Science 127, 229–254 (1994)

    Kari, J.: Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science 127, 229–254 (1994)

    1994

  16. [24]

    In: MFCS 2008

    Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: MFCS 2008. Lecture Notes in Computer Science, vol. 5162, pp. 419–430. Springer (2008), https://doi.org/10. 1007/978-3-540-85238-4_34

    2008

  17. [25]

    Société Mathématique de France (2003)

    K˚ urka, P.: Topological and symbolic dynamics. Société Mathématique de France (2003)

    2003

  18. [26]

    Cambridge university press (1997)

    Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge university press (1997)

    1997

  19. [27]

    Theoretical Computer Sci- ence 411(38-39), 3516–3526 (2010), https://doi.org/10.1016/j.tcs.2010.05.024

    Kutrib, M., Malcher, A.: Cellular automata with sparse communication. Theoretical Computer Sci- ence 411(38-39), 3516–3526 (2010), https://doi.org/10.1016/j.tcs.2010.05.024

    2010 doi

  20. [28]

    Theory of Computing Systems 48(3), 617–647 (2011), https://doi.org/10

    Lathrop, J.I., Lutz, J.H., Patitz, M.J., Summers, S.M.: Computability and complexity in self- assembly. Theory of Computing Systems 48(3), 617–647 (2011), https://doi.org/10. 1007/s00224-010-9252-0

    2011

  21. [29]

    Information and Control 32, 158–162 (1976)

    Maruoka, A., Kimura, M.: Condition for Injectivity of Global Maps for Tessellation Automata. Information and Control 32, 158–162 (1976)

    1976

  22. [30]

    Prentice Hall, Englewoods Cliffs (1967)

    Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall, Englewoods Cliffs (1967)

    1967

  23. [31]

    The- oretical Computer Science 292(3), 711–721 (2003), https://doi.org/10.1016/ S0304-3975(02)00065-8 Freezing, Bounded-Change and Convergent Cellular Automata 37

    Moreira, A.: Universality and decidability of number-conserving cellular automata. The- oretical Computer Science 292(3), 711–721 (2003), https://doi.org/10.1016/ S0304-3975(02)00065-8 Freezing, Bounded-Change and Convergent Cellular Automata 37

    2003

  24. [32]

    Transactions of the EICE 72(6), 758–762 (1989)

    Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. Transactions of the EICE 72(6), 758–762 (1989)

    1989

  25. [33]

    Journal de physique I 2(12), 2221–2229 (1992)

    Nagel, K., Schreckenberg, M.: A cellular automaton model for freeway traffic. Journal de physique I 2(12), 2221–2229 (1992)

    1992

  26. [34]

    In: ICALP 2006

    Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: ICALP 2006. Lecture Notes in Computer Science, vol. 4051, pp. 132–143. Springer (2006), https://doi.org/10. 1007/11786986_13

    2006

  27. [35]

    In: JAC 2008

    Ollinger, N.: Universalities in cellular automata a (short) survey. In: JAC 2008. pp. 102–118 (2008), https://hal.archives-ouvertes.fr/JAC2008/hal-00274563v1

    2008

  28. [36]

    Natural Computing 13(2), 195–224 (2014), https://doi.org/10.1007/s11047-013-9379-4

    Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Natural Computing 13(2), 195–224 (2014), https://doi.org/10.1007/s11047-013-9379-4

    2014 doi

  29. [37]

    In: DNA 2011

    Patitz, M.J., Schweller, R.T., Summers, S.M.: Exact shapes and turing universality at temperature 1 with a single negative glue. In: DNA 2011. Lecture Notes in Computer Science, vol. 6937, pp. 175–189. Springer (2011), https://doi.org/10.1007/978-3-642-23638-9_15

    2011 doi

  30. [38]

    In: Encyclopedia of Complexity and Systems Science, pp

    Pivato, M.: Ergodic theory of cellular automata. In: Encyclopedia of Complexity and Systems Science, pp. 2980–3015. Springer New York, New York, NY (2009), https://doi.org/10. 1007/978-0-387-30440-3_178

    2009

  31. [39]

    MIT Press (1967)

    Rogers, H.: Theory of Recursive Functions and Effective Computability. MIT Press (1967)

    1967

  32. [40]

    In: AUTOMATA & JAC

    Salo, V .: On nilpotency and asymptotic nilpotency of cellular automata. In: AUTOMATA & JAC

  33. [41]

    In: Handbook of Natural Com- puting, pp

    Terrier, V .: Language recognition by cellular automata. In: Handbook of Natural Com- puting, pp. 123–158. Springer, Berlin, Heidelberg (2012), https://doi.org/10.1007/ 978-3-540-92910-9_4

    2012

  34. [42]

    In: Burks, A.W

    Ulam, S.M.: On some mathematical problems connected with patterns of growth of figures. In: Burks, A.W. (ed.) Essays on Cellular Automata, pp. 219–231. U. of Illinois Press (1970)

    1970

  35. [43]

    In: Knödel, W., Schneider, H

    V ollmar, R.: On cellular automata with a finite number of state changes. In: Knödel, W., Schneider, H. (eds.) Parallel Processes and Related Automata / Parallele Prozesse und damit zusammenhän- gende Automaten, Computing Supplementum, vol. 3, pp. 181–191. Springer Vienna (1981)

    1981

  36. [44]

    In: AUTOMATA 2016

    Winslow, A.: A brief tour of theoretical tile self-assembly. In: AUTOMATA 2016. Lecture Notes in Computer Science, vol. 9664, pp. 26–31. Springer (2016), https://doi.org/10.1007/ 978-3-319-39300-1_3

    2016

  37. [45]

    In: STOC 1979

    Yao, A.C.C.: Some complexity questions related to distributive computing (preliminary report). In: STOC 1979. pp. 209–213 (1979)

    1979

  38. [2012]

    EPTCS, vol. 90, pp. 86–96 (2012), https://doi.org/10.4204/EPTCS.90.7

    2012 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.