Premium
On the threshold of chaos in random boolean cellular automata
Author(s) -
Lynch James F.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060212
Subject(s) - boolean function , mathematics , boolean network , parity function , discrete mathematics , state (computer science) , cellular automaton , boolean circuit , boolean model , bounded function , combinatorics , function (biology) , equivalence (formal languages) , product term , boolean expression , algorithm , two element boolean algebra , pure mathematics , algebra over a field , mathematical analysis , evolutionary biology , filtered algebra , biology
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 that the gate is assigned a constant function (respectively a noncanalyzing function, i.e., EQUIVALENCE or 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.