1993/09/16 by James F. Lynch, Lynch, James F.
Computer Science · Mathematics · Physics and Astronomy · #Adaptation and Self-Organizing Systems (nlin.AO) #Cellular Automata and Applications #FOS: Physical sciences #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.adap-org/9309001
openalex publication_date 1993/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A random boolean cellular automaton is a network of boolean gates where the inputs, the boolean function, and the initial state of each gate are chosen randomly. In this article, each gate has two inputs. Let a (respectively c) be the probability the the gate is assigned a constant function (respectively a non-canalyzing function, i.e., \sc equivalence or \sc exclusive or). Previous work has shown that when a > c, with probability asymptotic to 1, the random automaton exhibits very stable behavior: almost all of the gates stabilize, almost all of them are weak, i.e., they can be perturbed without affecting the state cycle that is entered, and the state cycle is bounded in size. This article gives evidence that the condition a = c is a threshold of chaotic behavior: with probability asymptotic to 1, almost all of the gates are still stable and weak, but the state cycle size is unbounded. In fact, the average state cycle size is superpolynomial in the number of gates.