pith. sign in

arxiv: 2604.15177 · v1 · submitted 2026-04-16 · 💻 cs.CC · cs.FL

Complexity of Fungal Automaton Prediction

Enrico Formenti , Eric Goles , K\'evin Perrot , Mart\'in R\'ios-Wilson , Domingo Ruiz-Tala This is my paper

Pith reviewed 2026-05-10 09:49 UTC · model grok-4.3

classification 💻 cs.CC cs.FL
keywords fungal automatafreezing totalistic rulesP-completenessprediction problemalternating rulesone-dimensional automatacomputational complexitymajority rule
0
0 comments X p. Extension

The pith

Predicting fungal automaton evolution under the freezing majority rule at radius 1.5 is P-complete.

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

The paper studies the complexity of forecasting future states in fungal automata, a grid-based model that applies one local rule alternately in the vertical and horizontal directions. For one-dimensional freezing totalistic rules of radius 1, the authors show that prediction falls into non-deterministic logspace for most cases, allowing efficient computation. One non-linear rule at this radius is left unresolved. The central result establishes that switching to the freezing majority rule at radius 1.5 makes the prediction problem P-complete. This matters because it links a simple nature-inspired local rule to the full power of polynomial-time computation when the alternating mechanism is used.

Core claim

While most fungal freezing totalistic one-dimensional rules of radius 1 admit non-deterministic logspace prediction algorithms, the freezing majority rule at radius 1.5 makes the prediction task P-complete under the alternating vertical-horizontal application.

What carries the argument

Alternating vertical and horizontal application of a single freezing totalistic rule on a one-dimensional lattice, with the majority rule serving as the example that reaches P-completeness when the radius is extended to 1.5.

Load-bearing premise

The model relies on the alternating vertical-horizontal application of the rules together with the exact definition of freezing totalistic rules at the stated radii.

What would settle it

An explicit logspace reduction from a known P-complete problem such as the circuit value problem to the prediction task for the radius-1.5 freezing majority rule, or conversely a non-deterministic logspace algorithm that correctly forecasts all configurations of that rule.

Figures

Figures reproduced from arXiv: 2604.15177 by Domingo Ruiz-Tala, Enrico Formenti, Eric Goles, K\'evin Perrot, Mart\'in R\'ios-Wilson.

Figure 1
Figure 1. Figure 1: In green, the connected component of cell [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The set of cells forming a staircase is shown in green. The size of the staircase is not fixed. All [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Let c be the configuration shown in the figure, where unlabeled cells are assumed to be in state 0. Consider the one-dimensional cellular automaton (f, {−1, 0, 1}, {0, 1}), where f(1, 0, 1) = 1, and f(a, b, c) = 0 for all other values a, b, c ∈ {0, 1}, and its associated fungal automaton (f, Q, M, HV, fH, fV ). The remaining grids depict successive updates of c under the global function FHV . Note that F 1… view at source ↗
Figure 4
Figure 4. Figure 4: Successive updates of the fungal automaton produced by the rule [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Configuration containing a staircase and a [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: In green we show an example of alliance, with all its cells initially in state [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Example of an alliance, and the unique type of configuration to which the dynamics converges: [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Successive updates of the fungal automaton associated with [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Example of an underlying graph associated with a configuration. On the left, a configuration [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Example of the grid constructed for a node [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Wire gadget represented in configuration [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Two wires of different parity. Note that all cells with value [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: In the top row, we define the following gadgets: (a) the [PITH_FULL_IMAGE:figures/full_fig_p017_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Crossing of wires. The figure shows two attempts of wire crossings. On the left, wires with [PITH_FULL_IMAGE:figures/full_fig_p018_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: For each i ∈ [m], each Ti represents a tile in this embedding of a circuit. Each tile has a fixed size O(m), which provides enough space for all wires carrying the bits corresponding to each input (depicted as blue lines) and to the outputs of all preceding gates (depicted in red). Tile Ti computes the output of gate Gi . The figure illustrates an example in which gate gi receives the wires corresponding … view at source ↗
Figure 16
Figure 16. Figure 16: Example of an embedding of the circuit with two input nodes [PITH_FULL_IMAGE:figures/full_fig_p022_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Neighborhood M for the FA F. For a cell x at coordinate (0, 0), the neighborhood M is highlighted in green. 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 c FHV (c, 1) FHV (c, 1) FHV (c, 2) [PITH_FULL_IMAGE:figures/full_fig_p023_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Updates of the FA F. On the left, the initial configuration c is shown, where unlabeled cells are assumed to have value 0. We note that FHV (c, 1) = fH(c) and FHV (c, 2) = fV [PITH_FULL_IMAGE:figures/full_fig_p023_18.png] view at source ↗
read the original abstract

Fungal automata are a nature-inspired computational model, where a rule is alternatively applied verticaly and horizontaly. In this work we study the computational complexity of predicting the dynamics of all fungal freezing totalistic one-dimentional rules of radius $1$, exhibiting various behaviors. Despite efficiently predictable in most cases (with non-deterministic logspace algorithms), a non-linear rule is left open to characterize. We further explore the freezing majority rule (which is totalistic), and prove that at radius $1.5$ it becomes $\mathbf{P}$-complete to predict.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript examines the computational complexity of predicting the evolution of fungal automata, defined as one-dimensional cellular automata where rules are applied alternately in vertical and horizontal directions. It classifies all freezing totalistic rules of radius 1, showing that most admit non-deterministic logspace (NL) prediction algorithms, leaving one non-linear rule open. Additionally, it proves that the freezing majority rule at radius 1.5 is P-complete to predict.

Significance. If the proofs hold, this provides a fine-grained complexity map for a biologically inspired variant of cellular automata, highlighting how the alternating application and radius affect predictability. The distinction between NL and P-completeness for similar rules is a useful contribution to the study of prediction problems in automata.

major comments (2)
  1. [Abstract] Abstract: the NL membership claims for radius-1 freezing totalistic rules and the P-completeness claim for the radius-1.5 freezing majority rule cannot be verified, as the specific algorithms, reductions (e.g., from CVP), and proof details are absent from the abstract; this is load-bearing for the central classification results.
  2. [Abstract] Abstract: the alternating vertical-horizontal application mechanism is taken as given without explicit definition or justification of how it interacts with the totalistic freezing constraint at radius 1 vs. 1.5; this needs clarification to confirm the reduction preserves the model.
minor comments (2)
  1. [Abstract] Abstract: typos include 'alternatively' (should be 'alternately'), 'verticaly' (should be 'vertically'), and 'one-dimentional' (should be 'one-dimensional').
  2. [Abstract] Abstract: the open non-linear rule at radius 1 should be identified by its explicit rule definition or number to allow readers to assess the gap.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address each major comment below. The detailed proofs are present in the body of the manuscript, but we agree the abstract can be strengthened for clarity and will revise it accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the NL membership claims for radius-1 freezing totalistic rules and the P-completeness claim for the radius-1.5 freezing majority rule cannot be verified, as the specific algorithms, reductions (e.g., from CVP), and proof details are absent from the abstract; this is load-bearing for the central classification results.

    Authors: The abstract is intentionally concise and does not contain full algorithmic or reduction details, which are instead provided in Sections 3 and 4. The NL membership for most radius-1 rules follows from a non-deterministic logspace procedure that guesses the order of vertical-then-horizontal updates and verifies local totalistic sums while respecting the freezing constraint (no 1-to-0 transitions). The P-completeness for the radius-1.5 majority rule is established by a direct reduction from the Circuit Value Problem, in which gate evaluations are simulated by majority votes over the alternating neighborhoods. We will revise the abstract to briefly reference these techniques (e.g., “via NL simulation of alternating updates” and “by reduction from CVP”) while remaining within length limits. revision: yes

  2. Referee: [Abstract] Abstract: the alternating vertical-horizontal application mechanism is taken as given without explicit definition or justification of how it interacts with the totalistic freezing constraint at radius 1 vs. 1.5; this needs clarification to confirm the reduction preserves the model.

    Authors: Section 2 defines the model explicitly: the one-dimensional lattice is embedded in a two-dimensional grid; the totalistic rule is first applied to vertical neighbors and then to horizontal neighbors. Radius 1 uses the four orthogonal neighbors; radius 1.5 additionally incorporates the four diagonal half-steps. Because the rule is totalistic (depends only on the neighbor sum) and freezing (a cell may change from 0 to 1 but never from 1 to 0), both the vertical and horizontal phases preserve these invariants. The CVP reduction is constructed so that every simulated gate respects the same freezing majority vote. We will insert a single clarifying sentence into the abstract and expand the model definition paragraph in the introduction to make the interaction explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard reductions

full rationale

The paper defines fungal automata as an alternating vertical-horizontal application of totalistic rules on a 1D grid and then classifies prediction complexity for freezing variants at radius 1 (mostly NL, one open) and proves P-completeness for the freezing majority rule at radius 1.5 via reduction from a known P-complete problem. These steps use external complexity-theoretic machinery (standard logspace reductions, circuit-value hardness) rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation. The model assumptions are stated upfront as the object of study, not derived from the complexity results themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the definition of the fungal automaton update scheme and standard complexity class properties; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard definitions and closure properties of NL and P complexity classes
    Invoked to classify prediction problems as NL or P-complete.
  • domain assumption The fungal automaton is defined by alternating vertical and horizontal rule applications on a 1D grid
    Core model definition used throughout the complexity analysis.

pith-pipeline@v0.9.0 · 5396 in / 1165 out tokens · 26028 ms · 2026-05-10T09:49:22.526342+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 2 canonical work pages

  1. [1]

    Modanese,A.,Worsch,T.: EmbeddingarbitraryBooleancircuitsintofungalautomata.Algorithmica, 1–23 (2024)

    2024

  2. [2]

    Oxford University Press (1995)

    Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995)

    1995

  3. [3]

    In: Adamatzky, A

    Adamatzky, A., Goles, E., Martínez, G.J., Tsompanas, M.-A., Tegelaar, M., Wösten, H.A.B.: Fungal automata. In: Adamatzky, A. (ed.)Fungal Machines: Sensing and Computing with Fungi, pp. 323–339. Springer, Berlin (2023)

    2023

  4. [4]

    In: Adamatzky, A

    Sepúlveda, C.S., Goles, E., Ríos-Wilson, M., Adamatzky, A.: Exploring dynamics of fungal cellular automata. In: Adamatzky, A. (ed.)Fungal Machines: Sensing and Computing with Fungi, pp. 341–370. Springer, Berlin (2023)

    2023

  5. [5]

    Physics Letters A384(22), 126541 (2020)

    Goles, E., Tsompanas, M.-A., Adamatzky, A., Tegelaar, M., Wösten, H.A.B., Martínez, G.J.: Computational universality of fungal sandpile automata. Physics Letters A384(22), 126541 (2020)

    2020

  6. [6]

    Fundamenta Informaticae171(1–4), 189–219 (2020)

    Formenti, E., Perrot, K.: How hard is it to predict sandpiles on lattices? A survey. Fundamenta Informaticae171(1–4), 189–219 (2020)

    2020

  7. [7]

    Miltersen,P.B.: Thecomputationalcomplexityofone-dimensionalsandpiles.TheoryofComputing Systems41(1), 119–125 (2007)

    2007

  8. [8]

    SIGACT News9(2), 25–29 (1977)

    Goldschlager, L.M.: The monotone and planar circuit value problems are log-space complete for P. SIGACT News9(2), 25–29 (1977)

    1977

  9. [9]

    Journal of Statistical Physics 96(1), 205–224 (1999)

    Moore, C., Nilsson, M.: The computational complexity of sandpiles. Journal of Statistical Physics 96(1), 205–224 (1999)

    1999

  10. [10]

    Physical Review Letters59(4), 381–384 (1987)

    Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality: An explanation of the1/f noise. Physical Review Letters59(4), 381–384 (1987)

    1987

  11. [11]

    Theoretical Computer Science997, 114511 (2024)

    Ríos-Wilson, M., Theyssier, G.: Intrinsic universality in automata networks I: Families and simulations. Theoretical Computer Science997, 114511 (2024)

    2024

  12. [12]

    arXiv:2511.09297 (2025)

    Goles, E., Montealegre, P., Ríos-Wilson, M., Theyssier, G.: On the complexity of freezing automata networks of bounded pathwidth. arXiv:2511.09297 (2025)

    work page arXiv 2025

  13. [13]

    Journal of Computer and System Sciences22(3), 365–383 (1981)

    Ruzzo, W.L.: On uniform circuit complexity. Journal of Computer and System Sciences22(3), 365–383 (1981)

    1981

  14. [14]

    Theoretical Computer Science1016, 114779 (2024)

    Ríos-Wilson,M.,Theyssier,G.: IntrinsicuniversalityinautomatanetworksII:Glueingandgadgets. Theoretical Computer Science1016, 114779 (2024)

    2024

  15. [15]

    Theoretical Computer Science1022, 114890 (2024)

    Ríos-Wilson, M., Theyssier, G.: Intrinsic universality in automata networks III: On symmetry versus asynchrony. Theoretical Computer Science1022, 114890 (2024)

    2024

  16. [16]

    Information and Computation274, 104537 (2020)

    Goles,E.,Montealegre,P.: Thecomplexityoftheasynchronouspredictionofthemajorityautomata. Information and Computation274, 104537 (2020)

    2020

  17. [17]

    Advances in Applied Mathematics125, 102161 (2021) 20

    Goles, E., Montealegre, P., Perrot, K.: Freezing sandpiles and Boolean threshold networks: Equivalence and complexity. Advances in Applied Mathematics125, 102161 (2021) 20

    2021

  18. [18]

    Ríos-Wilson, M

    Goles, E., Montealegre, P. Ríos-Wilson, M. Theyssier, G.: On the parameterized complexity of freezing dynamics, Advances in Applied Mathematics157, 102706 (2024)

    2024

  19. [19]

    Theoretical Computer Science609, 118–128 (2016)

    Goles, E., Montealegre, P., Salo, V., Törmä, I.: PSPACE-completeness of majority automata networks. Theoretical Computer Science609, 118–128 (2016)

    2016

  20. [20]

    Information and Computation281, 104764 (2021)

    Goles, E., Maldonado, D., Montealegre, P., Ríos-Wilson, M.: On the complexity of asynchronous freezing cellular automata. Information and Computation281, 104764 (2021)

    2021

  21. [21]

    Natural Computing24(1), 29–66 (2025)

    Concha-Vega, P., Goles, E., Montealegre, P., Perrot, K.: Sandpiles prediction and crossover onZ2 within Moore neighborhood. Natural Computing24(1), 29–66 (2025)

    2025

  22. [22]

    Discrete Mathematics & Theoretical Computer Science24(1) (2022)

    Ollinger, N., Theyssier, G.: Freezing, bounded-change and convergent cellular automata. Discrete Mathematics & Theoretical Computer Science24(1) (2022)

    2022

  23. [23]

    Nakar,Y.,Ron,D.: Characterizingandtestingconfigurationstabilityintwo-dimensionalthreshold cellular automata. arXiv:2507.14569 (2025) 21 10101010101010101101 10 0101010101011 10 01 1 10 0 010101011 1 10 0 01 1 1 11 0 0 0 10010101010101010101011 0 0 0 10 1 1 11 1 1 0 0 00101000101 1 1 11 11 0 0 00 1001 1 1 11 1 0 0 01 0 0 1 1 1010101010101010101010101010101...

    work page arXiv 2025