An NK
automaton is an autonomous random network of N Boolean
logic elements. Each element has K inputs and one output.
The signals at inputs and outputs take binary (0 or 1) values.
The Boolean elements of the network and the connections between
elements are chosen in a random manner. There are no external
inputs to the network. The number of elements N is assumed
to be large.
An automaton operates in discrete time. The set of the output
signals of the Boolean elements at a given moment of time
characterizes a current state of an automaton. During an
automaton operation, the sequence of states converges to a cyclic
attractor. The states of an attractor can be considered as a
"program" of an automaton operation. The number of
attractors M and the typical attractor length L are
important characteristics of NK automata.
The automaton behavior depends essentially on the connection
degree K.
If K is large (K = N), the behavior is
essentially stochastic. The successive states are random with
respect to the preceding ones. The "programs" are very
sensitive to minimal disturbances (a minimal disturbance is a
change of an output of a particular element during an automaton
operation) and to mutations (changes in Boolean element types
and in network connections). The attractor lengths L are
very large: L ~ 2N/2 . The number
of attractors M is of the order of N. If the
connection degree K is decreased, this stochastic type of
behavior is still observed, until K ~ 2.
At K ~ 2 the network behavior changes drastically. The
sensitivity to minimal disturbances is small. The mutations
create typically only slight variations an automaton dynamics.
Only some rare mutations evoke the radical, cascading changes in
the automata "programs". The attractor length L and
the number of attractors M are of the order of N1/2.
This is the behavior at the edge of chaos, at the borderland
between chaos and order.
The NK automata can be considered as a model of
regulatory genetic systems of living cells. Indeed, if we
consider any protein synthesis (gene expression) as regulated by
other proteins, we can approximate a regulatory scheme of
a particular gene expression by a Boolean element, so that a complete
network of molecular-genetic regulations of a cell can be
represented as a network of a NK automaton.
S.A.Kauffman argues that the case K ~ 2 is just
appropriate to model the regulatory genetic systems of biological
cellular organisms, especially in evolutionary context. The main
points of this argumentation are as follows:
- the regulatory genetic systems at the edge of chaos ensure both necessary
stability and potential for progressive evolutionary
improvements;
- typical cellular gene regulation schemes include only a
small number of inputs from other genes in accordance with the
value K ~ 2;
- if we compare the number of automaton attractors M at
K = 2 (calculated for given number of genes N) with
the number of different kind of cells ncells
in biological organisms at various evolutionary levels, we find
similar values; for example, for a human we have (N ~
105): M = 370, ncells =
254 [4].
Because the regulatory structures at the edge of chaos (K
~ 2) ensure both stability and evolutionary improvements, they
could provide the background conditions for an evolution of
genetic cybernetic systems. That is, such systems have "the
ability to evolve". So, it seems quite plausible, that such
kind of regulatory genetic structures was selected at early
stages of life, and this in turn made possible the further
progressive evolution.
References
S. A. Kauffman. Scientific American. 1991. August.
P. 64.
S. A. Kauffman. 
The Origins of Order: Self-Organization and Selection in Evolution, Oxford University Press, New York, 1993.
S. A. Kauffman.At Home in the Universe: The Search for Laws of Self-Organization and Complexity, Oxford University Press, Oxford, 1995.
