On Symmetry Versus Asynchronism: At the Edge of Universality in Automata Networks

The paper proves that there exists a fixed b such that AND–OR networks under a block‑sequential scheme are strongly universal by (i) establishing strong universality for signed symmetric conjunctive networks with a constant number of blocks via carefully clocked, self‑cleaning gadgets, and then (ii) reducing those to AND–OR networks in constant time using a double‑rail trick; this is stated explicitly as Theorem 49 and relies on Lemma 48 and Corollary 8 . The candidate model attempts a direct, circuit‑style construction in monotone AND/OR networks using pipelines, splitters, and one‑hot NAND gates with a 5‑phase schedule. However, it fails to address the fundamental bidirectionality of edges and monotonicity: undirected OR/AND nodes necessarily read all neighbors symmetrically, so the proposed “directed” pipelines and splitters suffer from back‑flow and sticky-1 memory, and the output nodes cannot be connected to downstream buffers without those buffers also influencing the output nodes. The paper explicitly confronts these issues with clocks and erasure mechanisms in its gadgets , while the model’s design assumes them away.