The Complexity of Computations in Recurrent Boolean Networks
Sergey A. Shumsky
P. N. Lebedev Physical Institute,
Leninsky pr.53, Moscow, Russia
Abstract
This paper considers the amount of information processed in boolean automata networks with random interconnections. The complexity of computations is defined as the number of logical switchings during the run. The distribution of automata types in the network gives rise to a distribution of computational complexity with various initial conditions. We calculate this complexity distribution and find the limits of complexity in the individual algorithms.
