Hierarchical Self-Organization
in the Finitary Process Soup
Abstract Current analyses of genomes from numerous species
show that the diversity of their functional and behavioral characters is
not proportional to the number of genes that encode the organism.
We investigate the hypothesis that the diversity of organismal
character is due to hierarchical organization. We do this with the
recently introduced model of the finitary process soup, which allows
for a detailed mathematical and quantitative analysis of the population
dynamics of structural complexity. Here we show that global
complexity in the finitary process soup is due to the emergence
of successively higher levels of organization, that the hierarchical
structure appears spontaneously, and that the process of structural
innovation is facilitated by the discovery and maintenance of relatively
noncomplex, but general, individuals in a population.
Olof Go¨ rnerup*,**,z
Chalmers University of Technology
Santa Fe Institute
James P. Crutchfieldy,z
University of California, Davis
Santa Fe Institute
Keywords
Pre-biotic evolution, structural complexity,
hierarchy, self-organization, networks,
population dynamics
l
D
o
w
N
o
UN
D
e
D
F
R
o
M
H
T
T
P
:
/
/
D
io
R
e
C
T
.
M
io
T
.
e
D
tu
UN
R
T
l
/
/
l
UN
R
T
io
C
e
–
P
D
F
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
UN
R
T
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
P
D
.
.
F
B
sì
G
tu
e
S
T
T
o
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
1 introduzione
Recent estimates have shown that the genomes of many species consist of a surprisingly similar
number of genes despite some species being markedly more sophisticated and diverse in their be-
haviors. Humans have only 30% more genes that the worm Caenorhabditis elegans; humans, mice, E
rats have nearly the same number [15, 18]. Inoltre, many of those genes serve to maintain ele-
mentary processes and are shared across species, which greatly reduces the number of genes available
to account for diversity. One concludes that individual genes cannot directly code for the full array of
individual functional and morphological characters of a species, as genetic determinism would have it.
From what, Poi, do the sophistication and diversity of organismal form and behavior arise?
Here we investigate the hypothesis that these derive from a hierarchy of interactions between
genes and between interacting gene complexes. A hierarchy of gene interactions, being composed of
subsets of available genes, allows for an exponentially larger range of functions and behaviors than
direct gene-to-function coding. We will use a recently introduced pre-biotic evolutionary model —
the finitary process soup — of the population dynamics of structural complexity [6]. Specifically, we
will show that global complexity in the finitary process soup is due to the emergence of succes-
sively higher levels of organization. Importantly, hierarchical structure appears spontaneously and is
* Corresponding author
** Department of Physical Resource Theory, Chalmers University of Technology, 412 96 Go¨ teborg, Sweden. E-mail: olof.gornerup@
fy.chalmers.se
y Center for Computational Science & Engineering and Physics Department, University of California, Davis, One Shields Avenue, Davis
CA 95616. E-mail: chaos@cse.ucdavis.edu
z Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501.
N 2008 Istituto di Tecnologia del Massachussetts
Artificial Life 14: 245 – 254 (2008)
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
facilitated by the discovery and maintenance of relatively noncomplex, but general individuals in a
population. These results, in concert with the minimal assumptions and simplicity of the finitary
process soup, strongly suggest that an evolving system’s sophistication, complexity, and functional
diversity derive from its hierarchical organization.
2 Modeling Pre-biology
Prior to the existence of highly sophisticated entities acted on by evolutionary forces, replicative
objects relied on far more basic mechanisms for maintenance and growth. Tuttavia, these objects
managed to transform not only themselves, but also indirectly the very transformations by which
they changed [20], eventually supporting the mechanisms of natural selection. How did the transition
from raw interaction to evolutionary change take place? Is it possible to pinpoint generic properties,
however basic, that would have enabled a system of simple interacting objects to take the first few
steps toward biotic organization?
To explore these questions in terms of structural complexity we developed a theoretical model
borrowing from computation theory [13] and computational mechanics [9, 5]. In this system —the
finitary process soup — elementary objects, as represented by e-machines, interact and generate new
objects in a well-stirred flow reactor.
Choosing e-machines as the interacting, replicating objects,
it turns out, brings a number of
advantages. Most particularly, there is a well-developed theory of their structural properties found in
the framework of computational mechanics. In contrast with individuals in previous, related pre-
biotic models — such as machine language programs [16, 17, 19, 1], tags [10, 2], E-expressions [11],
and cellular automata [7], e-machines have a well-defined (and calculable) notion of structural
complexity. For the cases of machine language and E calculus, in contrast, it is known that algorithms
do not even exist to calculate such properties, since these representations are computation-universal
[3]. Another important distinction with prior pre-biotic models is that the individuals in the finitary
process soup do not have two separate modes of operation— one of representation or storage
and one for functioning and transformation. The individuals are simply objects whose internal
structure determines how they interact. The benefit of this when modeling prebiotic evolution is that
there is no assumed distinction between gene and protein [21, 24] or between data and program
[16, 17, 19, 1, 14].
3 e-Machines
Individuals in the finitary process soup are objects that store and transform information. Nel
vocabulary of information theory, they are communication channels [4]. Here we focus on a type of
finite-memory channel, called a finitary e-machine, as our preferred representation of an evolving
information-processing individual. To understand what this choice captures, we can think of these
individuals in terms of how they compactly describe stochastic processes.
A process is a discrete-valued, discrete-time stationary stochastic information source [4]. A process
is most directly described by the bi-infinite sequence it produces of random variables St over an
alphabet A:
X
S
¼ . . . St(cid:4)1St Stþ1. . .
ð1Þ
X
and the distribution P(S
) over those sequences. At each moment t, we think of the bi-infinite
P
!
t = StSt +1 St +2 . . . sub-
t = . . . St(cid:4)3 St(cid:4)2St(cid:4)1 and a future S
sequence as consisting of a history S
X
!
P
= S
t S
sequence: S
T.
246
Artificial Life Volume 14, Numero 3
l
D
o
w
N
o
UN
D
e
D
F
R
o
M
H
T
T
P
:
/
/
D
io
R
e
C
T
.
M
io
T
.
e
D
tu
UN
R
T
l
/
/
l
UN
R
T
io
C
e
–
P
D
F
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
UN
R
T
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
P
D
.
.
F
B
sì
G
tu
e
S
T
T
o
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
A process stores information in its set S of causal states. Mathematically, these are the members of
from histories to sets of histories,
the range of the map e : S
p i 2S
P
e(cid:1) sp(cid:2) ¼ (cid:3) spV(cid:4)
(cid:4)P(cid:1)
!(cid:4)
S
P
(cid:4) S
¼ sp(cid:2) ¼ P(cid:1)
!(cid:4)
S
P
(cid:4) S
¼ spV(cid:2)(cid:5);
ð2Þ
P
P
is the power set of histories S
. Questo è, the causal state S of a history sp is the set of histories
where 2S
that all have the same probability distribution of futures. The transition from one causal state Si to
another Sj while emitting the symbol s a A is given by a set of labeled transition matrices: T =
(cid:3)T ðsÞ
: s a A(cid:5), in which
ij
l
D
o
w
N
o
UN
D
e
D
F
R
o
M
H
T
T
P
:
/
/
D
io
R
e
C
T
.
M
io
T
.
e
D
tu
UN
R
T
l
/
/
l
UN
R
T
io
C
e
–
P
D
F
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
UN
R
T
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
P
D
.
.
F
B
sì
G
tu
e
S
T
T
o
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
ij u P(cid:1)SV ¼ Sj ;
T ðsÞ
!1 ¼ s(cid:4)
S
(cid:4)S ¼ Si
(cid:2);
ð3Þ
!1
where S is the current casual state, SV its successor, and S
the next symbol in the sequence.
A process’ e-machine is the ordered pair {S, T }. Finitary e-machines are stochastic finite-state
machines with the following properties [9]: (io) All recurrent states form a single strongly connected
component. (ii) All transitions are deterministic in the specific sense that a causal state together with
the next symbol determines a unique next state. (iii) The set of causal states is finite and minimal.
In the finitary process soup we use the alphabet A = {0|0, 0|1, 1|0, 1|1} consisting of pairs in|out of
input and output symbols over a binary alphabet B = {0, 1}. When used in this way, e-machines read in
strings over B and emit strings over B. Accordingly, they should be viewed as mappings from one process
X
X
input to another S
S
produzione. They are, Infatti, simply functions, each with a domain (the set of strings that can
be read) and with a range (the set of strings that can be produced). In this way, we consider e-machines as
models of objects that store and transform information. In the following we will take the transitions from
each causal state to have equal probabilities. Figura 1 shows several examples of simple e-machines.
Given that e-machines are transformations, one can ask how much processing they do—how
much structure do they add to the inputs when producing an output? Due to the properties mentioned
above, one can answer this question precisely. Ignoring input and output symbols, the state-to-state
S a A T ðSÞ. IL
transition probabilities are given by an e-machine’s stochastic connection matrix: T u
causal-state probability distribution pS is given by the left eigenvector of T associated with eigenvalue 1
and normalized in probability. If M is an e-machine, then the amount of information storage that it has,
and that it can add to an input process, is given by M’s structural complexity
P
CAðMÞ u (cid:4)
X
v a S
pSðvÞ log2 pSðvÞ:
4 :-Machine Interaction
ð4Þ
e-machines interact by functional composition. Two machines TA and TB that act on each other
result in a third TC ¼ TB B TA, where TC (io) has the domain of TA and the range of TB and (ii) È
Figura 1. Example e-machines: TA has a single causal state and, according to its transition labels, is the identity function. TB
consists of causal states A and B and two transitions. TB accepts two input strings, either 1010 . . . O 0101 . . . , and flips 0s
to 1s and vice versa as it produces an output string. Note that the function’s domain and range are the same. TC has the
same domain and range as TB, but does not exchange 0s and 1s.
Artificial Life Volume 14, Numero 3
247
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
Figura 2. Interaction network for the e-machines of Figure 1. It is a meta-machine.
minimized. If TA and TB are incompatible (per esempio., the domain of TB does not overlap with the range of
TA), the interaction produces nothing — it is considered elastic. During composition the size of the
resulting e machine can grow very rapidly (geometrically): |TC| V |TB| (cid:11) |TA|.
4.1 Interaction Network
We monitor the interactions of objects in the soup via the interaction network G. This is represented as
a graph whose nodes correspond to e-machines and whose transitions correspond to interactions. If
Tk ¼ Tj B Ti occurs in the soup, then the edge from Ti to Tk is labeled Tj. One can represent G with
the binary matrices:
GðkÞ
ij ¼
8
<
:
1 if Tk ¼ Tj B Ti ;
0 otherwise:
ð5Þ
For the set of e-machines in Figure 1, for example, we have the interaction graph shown in Figure 2
that is given by the matrices
GðAÞ ¼
2
6
6
6
6
4
1 0
0 0
0 0
3
7
7
7
7
5
;
0
0
0
GðBÞ ¼
2
6
6
6
6
4
0
1
0
1
0
1
3
7
7
7
7
5
;
0
1
0
and GðCÞ ¼
2
6
6
6
6
4
0
0
1
0
1
0
3
7
7
7
7
5
:
1
0
1
To measure the diversity of interactions in a population we define the interaction network complexity
CAðGÞ ¼ (cid:4)
X
fi ; fj ; fk>0
vk
ij
V k log2
vk
ij
V k
;
Dove
vk
ij ¼
8
<
fi fj
:
0
248
if Tk ¼ Tj B Ti has occurred;
otherwise;
ð6Þ
ð7Þ
Artificial Life Volume 14, Number 3
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
a
r
t
l
/
/
l
a
r
t
i
c
e
-
p
d
f
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
a
r
t
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
p
d
.
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
k is a normalizing factor, and fi is the fraction of e-machine type i in the soup. In order
V k = Slm vlm
to emphasize our interest in actual reproduction pathways, we consider only those that have oc-
curred in the soup.
4.2 Meta-machines
Given a population P of e-machines, we define a meta-machine V o P to be a connected set of
e-machines that is invariant under composition. That is, V is a meta-machine if and only if (i)
Tj B Ti a V for all Ti, Tj a V, (ii) for all Tk a V, there exists Ti, Tj a V such that Tk ¼ Tj B Ti, and
(iii) there is a nondirected path between every pair of nodes in V’s interaction network GV. The
interactions in Figure 2 describe a meta-machine of Figure 1’s e-machines.
The meta-machine captures the notion of a self-replicating and autonomous entity and is con-
sistent with Maturana and Varela’s autopoietic set [23], Eigen and Schuster’s hypercycle [22], and Fontana
and Buss’ organization [12].
5 Population Dynamics
We employ a continuously stirred flow reactor with an influx rate Ain that consists of a population P
of N e-machines. The dynamics of the population is iteratively ruled by compositions and replace-
ments as follows:
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
a
r
t
l
/
/
l
a
r
t
i
c
e
-
p
d
f
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
a
r
t
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
p
d
.
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
1. e-machine Generation:
(a) With probability Ain generate a random e-machine TR (influx).
(b) With probability 1 (cid:4) Ain (reaction):
i. Select TA and TB randomly.
ii. Form the composition TC ¼ TB B TA.
2. e-machine Outflux:
(a) Select an e machine TD randomly from the population.
(b) Replace TD with either TC or TR.
Below, TR will be uniformly sampled from the set of all two-state e-machines. This set is also used
when initializing the population. The insertion of TR corresponds to the influx, while the removal of
TD corresponds to the outflux. The latter keeps the population size constant. Note that there is no
spatial dependence in this model; e-machines are picked uniformly from the population for each
replication. The finitary process soup here is a well-stirred gas of reacting objects.
When there is no influx (Ain = 0) and the population is closed with respect to composition, the
population dynamics is described by a finite-dimensional set of equations:
t ¼ f t(cid:4)1 (cid:13) GðkÞ
f ðkÞ
ij
(cid:13) f T
t(cid:4)1Z(cid:4)1;
where ft
(k) is the frequency of e-machine type k at time t, and Z(cid:4)1 is a normalization factor.
Artificial Life Volume 14, Number 3
ð8Þ
249
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
In addition to capturing the notion of self-replicating entities, meta-machines also describe an
important type of invariant set of the population dynamics. Formally, we have
V ¼ G B V;
ð9Þ
where V is a meta-machine and G is the interaction network. These invariant sets can be stable
or unstable under the population dynamics. Note that the meta-machine of Figure 2 is unstable:
Only TA produces TAs. Thus, over time the population dynamics will decay to the meta-machine of
Figure 3, which describes a soup consisting only of TBs and TCs. This example also happens to
illustrate that copying —implemented here by the identity object TA —need not dominate the pop-
ulation and so does not have to be removed by hand, as done in several prior pre-biotic models. It
can decay away due to the intrinsic population dynamics.
6 Simulations
A system constrained by closure forms one useful base case that allows for a straightforward analysis
of the population dynamics. It does not permit, however, for the innovation of structural novelties in
the soup on either the level of individual objects (e-machines) or the level of their interactions. What
we are interested in is the possibility of open-ended evolution of e-machines and their meta-
machines. When enabled as an open system, both with respect to composition and influx, the soup
constitutes a constructive dynamical system and the population dynamics of Equation 8 do not
strictly apply. (The open-ended population dynamics of epochal evolution is required [8].)
We first set the influx rate to zero in order to study dynamics that are ruled only by compositional
transformations. One important first observation is that almost the complete set of machine types
that are represented in the soup’s initial random population is replaced over time. Thus, even at the
earliest times, the soup generates genuine novelty. The population-averaged individual complexity
hCA(T )i increases initially, as Figure 4a (Ain c 0) from [6] shows. The e-machines are to some
extent shaped by the selective pressure coming from outflux and by geometric growth due to
composition. The turnover is due to the dominance of nonreproducing e-machines in the initial
population. hCA(T )i subsequently declines, since it is favorable to be simple in that it takes a more
extensive stochastic search to find reproductive interactions that include more complex e-machines.
Note (Figure 4b, Ain c 0) that the run-averaged interaction complexity hCA(G )i reaches a sig-
nificantly higher value than hCA(T )i, implying that the population’s structural complexity derives
from its network of interactions rather than the complexity of its constituent individuals. hCA(G )i
continues to grow while compositional paths are discovered and created. A maximum is eventually
reached after which hCA(G )i declines and settles down to zero when one single type of self-reproducing
e-machine takes over the whole population.
By monitoring the individual run values of CA(G ) rather than the ensemble average, one sees
that they form plateaus as shown in Figure 5. The plateaus—at CA(G ) = 4 bits and, most notably, at
CA(G ) = 2 bits and 0 bits—are determined by the largest meta-machine that is present at a given time.
Being a closed set, the meta-machine does not allow any novel e-machines to survive, and this gives the
upper bound on CA(G). As one e-machine type is removed from V by the outflux, the meta-machine
Figure 3. The meta-machine to which that in Figure 2 decays under the population dynamics of Equation 8.
250
Artificial Life Volume 14, Number 3
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
a
r
t
l
/
/
l
a
r
t
i
c
e
-
p
d
f
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
a
r
t
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
p
d
.
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
Figure 4 . (a) Population-averaged e-machine complexity hCA(T )i and (b) run-averaged interaction network complexity
hCA(G)i as a function of time t and influx rate Ain for a population of N = 100 objects. (Reprinted with permission
from [6].)
decomposes and the upper bound on CA(G) lowers. This produces a stepwise and irreversible suc-
cession of meta-machine decompositions.
Thus, in the case of zero influx, one sees that the soup moves from one extreme to another. It is
completely disordered initially, generates structural complexity in its individuals and in its interaction
network, runs out of resources (poorly reproducing e-machines that are consumed by outflux), and
decomposes down to a single type of simple self-reproducing e-machine.
Although Figure 5 shows only three plateaus, there is in principle one plateau for every meta-
machine that at some point is the largest one generated by the soup. The diagram in Figure 6
summarizes our results from a more extensive and systematic survey of meta-machine hierarchies
from a series of runs with N = 500. It gives one illuminating example of how the soup spon-
taneously generates hierarchies of meta-machines.
Leaving closed soups behind, we now investigate the effects of influx. Recall the population-
averaged e-machine complexity hCA(T )i and the run-averaged interaction network complexity hCA(G )i
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
a
r
t
l
/
/
l
a
r
t
i
c
e
-
p
d
f
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
a
r
t
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
p
d
.
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Figure 5. Meta-machine decomposition in a closed soup: 15 separate runs with N = 500 that illustrate the typical
behaviors. While the minimal four-element meta-machine V4 (shown) dominates the soup, CA(G) is bounded by 4 bits.
Once outflux removes one of its e-machines, V4 decays rapidly to V2, a two-element meta-machine (shown). (V4 does
not contain a sub-meta-machine of three e-machines.) At this point CA(G) is bounded by 2 bits. After some period of
time, V2 decays to V1, a single self-reproducing e machine (shown), and CA(G) is fixed at 0.
Artificial Life Volume 14, Number 3
251
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
a
r
t
l
/
/
l
a
r
t
i
c
e
-
p
d
f
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
a
r
t
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
p
d
.
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Figure 6. Meta-machine hierarchy of dynamical composition and decomposition. Dots denote e-machines. An isolated
TA TC transitions.
dot denotes a self-replicating e-machine. Solid lines denote TA !TB TC transitions. Dashed lines denote TB !
Although all possible transitions are used by the meta-machines shown, they are represented in a simplified way accord-
ing to V4; cf. Figure 5.
as a function of t and Ain shown in Figure 4. Over time, hCA(T )i behaves similarly for Ain > 0 to the
way it does when Ain = 0. It increases rapidly initially, reaches a peak, and declines to a steady state.
Notably, the emergence of complex organizations of interaction networks occurs where the average
structural complexity of the e-machines is low. Stationary hCA(T )i is instead maximized at a relatively
high influx rate (Ain c 0.75), at which hCA(G )i is small compared to its maximum. As Ain is increased,
so is hCA(G )i at large times. hCA(G )i is maximized around Ain c 0.1. For higher influx rates, indi-
vidual novelty has a deleterious effect on the sophistication of a population’s interaction network.
Existing reproductive paths do not persist due to the low rate of successful compositions of highly
structured, and therefore specialized, individuals. We found that the maximum network complexity
cCAðGÞ grows slowly and linearly over time at c7.6 (cid:11) 10(cid:4)4 bits/replication.
7 Summary and Conclusions
To understand the basic mechanisms driving the evolutionary emergence of structural complexity in
a quantitative and tractable pre-biotic setting, we investigated a well-stirred soup of e-machines
(finite-memory communication channels) that react with each other by composition and so generate
new e-machines. When the soup is open with respect to composition and influx, it spontaneously
builds structural complexity on the level of transformative relations among the e-machines rather
252
Artificial Life Volume 14, Numero 3
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
than in the e-machine individuals themselves. This growth is facilitated by the use of relatively non-
complex individuals that represent general and elementary local functions rather than highly spe-
cialized individuals. The soup thus maintains local simplicity and generality in order to build up
hierarchical structures that support global complexity.
Novel computational representations are intrinsically introduced in the form of meta-machines
Quello, in turn, are interrelated in a hierarchy of composition and decomposition. Computationally
powerful local representations are thus not necessary (nor effective) in order for the emergence and
growth of complex replicative processes in the finitary process soup.
Meta-machines in closed soups eventually decay. For CA(G ) to maintain itself and grow, the soup
must be fed with novel material in the form of random e-machines. Otherwise, any spontaneously
generated meta-machines are decomposed (due to finite-population sampling), and the population
eventually consists of a single type of trivially self-reproducing e-machine. At an intermediate influx
rate, Tuttavia, the interaction network complexity is not only maintained but grows linearly with time.
Questo, Poi, suggests the possibility of open-ended evolution of increasingly sophisticated organizations.
Ringraziamenti
This work was supported at the Santa Fe Institute under the Network Dynamics Program funded by
the Intel Corporation and under the Computation, Dynamics, and Inference Program via SFI’s core
grants from the National Science and MacArthur Foundations. Direct support was provided by NSF
grants DMR9820816 and PHY9910217 and DARPA Agreement F306020020583. O.G. was partially
funded by PACE (Programmable Artificial Cell Evolution), a European Integrated Project in the EU
FP6-IST-FET Complex Systems Initiative.
Riferimenti
1. Adami, C., & Brown, C. T. (1994). Evolutionary learning in the 2D artificial life system ‘Avida’. In
Artificial Life 4 (pag. 377 – 381). Cambridge, MA: CON Premere.
2. Bagley, R. J., Farmer, J. D., Kauffman, S. A., Packard, N. H., Perelson, UN. S., & Stadnyk, IO. M.
(1989). Modeling adaptive biological systems. Biosystems, 23, 113 – 138.
3. Brookshear, J. G. (1989). Theory of computation: Formal languages, automata, and complexity. Benjamin/
Cummings.
4. Cover, T. M., & Thomas, J. UN. (1991). Elements of information theory. New York: Wiley-Interscience.
5. Crutchfield, J. P. (1994). The calculi of emergence: Computation, dynamics, and induction. Physica D,
75, 11 – 54.
6. Crutchfield, J. P., & Go¨rnerup, O. (2006). Objects that make objects: The population dynamics of
structural complexity. Journal of the Royal Society Interface, 3, 345 – 349; doi:10.1098/rsif.2006.0114.
7. Crutchfield, J. P., & Mitchell, M. (1995). The evolution of emergent computation. Atti del
National Academy of Sciences of the U.S.A., 92, 10742 – 10746.
8. Crutchfield, J. P., & van Nimwegen, E. (2002). The evolutionary unfolding of complexity. In
l. F. Landweber & E. Winfree (Eds.), Evolution as computation (pag. 67 – 94). New York:
Springer-Verlag; Santa Fe Institute Working Paper 99-02-015; adap-org/9903001.
9. Crutchfield, J. P., & Young, K. (1989). Inferring statistical complexity. Physical Review Letters, 63, 105 – 108.
10. Farmer, J. D., Packard, N. H., & Perelson, UN. S. (1986). The immune system, adaptation, E
machine learning. Physica D, 2, 187 – 204.
11. Fontana, W. (1991). Algorithmic chemistry. In C. Langton, C. Taylor, J. D. Farmer, & S. Rasmussen
(Eds.), Artificial Life II (pag. 159 – 209). Reading, MA: Addison-Wesley.
12. Fontana, W., & Buss, l. W. (1996). The barrier of objects: From dynamical systems to bounded
organizations. In S. Casti & UN. Karlqvist (Eds.), Boundaries and barriers (pag. 56 – 116). Reading, MA:
Addison-Wesley.
13. Hopcroft, J. E., & Ullman, J. D. (1979). Introduction to automata theory, languages, and computation. Reading, MA:
Addison-Wesley.
Artificial Life Volume 14, Numero 3
253
l
D
o
w
N
o
UN
D
e
D
F
R
o
M
H
T
T
P
:
/
/
D
io
R
e
C
T
.
M
io
T
.
e
D
tu
UN
R
T
l
/
/
l
UN
R
T
io
C
e
–
P
D
F
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
UN
R
T
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
P
D
.
.
F
B
sì
G
tu
e
S
T
T
o
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
O. Go¨rnerup and J. P. Crutchfield
Hierarchical Self-Organization in the Finitary Process Soup
14. Ikegami, T., & Hashimoto, T. (1997). Replication and diversity in machine-tape coevolutionary systems.
In C. G. Langton & K. Shimohara (Eds.), Artificial Life V: Proceedings of the Fifth International Workshop
on the Synthesis and Simulation of Living Systems (pag. 426 – 433). Cambridge, MA: CON Premere.
15. Lynch, M., & Conery, J. S. (2003). The origins of genome complexity. Scienza, 302, 1401 – 1404.
16. Rasmussen, S., Knudsen, C., Feldberg, P., & Hindsholm, M. (1990). The coreworld: Emergence
and evolution of cooperative structures in a computational chemistry. In S. Forrest (Ed.), Emergent
Computation (pag. 111 – 134). Amsterdam: North-Holland.
17. Rasmussen, S., Knudsen, C., & Feldberg, R. (1992). Dynamics of programmable matter. In Artificial
Life II: Proceedings of an Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems. Reading, MA:
Addison-Wesley.
18. Rat Genome Sequencing Project Consortium. (2004). Genome sequence of the brown Norway rat
yields insights into mammalian evolution. Nature, 428, 493 – 521.
19. Ray, T. S. (1991). An approach to the synthesis of life. In C. Langton, C. Taylor, J. D. Farmer,
& S. Rasmussen (Eds.), Artificial Life II (pag. 371 – 408). Reading, MA: Addison-Wesley.
20. Ro¨ssler, O. (1979). Recursive evolution. BioSystems, 11, 193 – 199.
21. Schro¨dinger, E. (1967). What is life? Mind and matter. Cambridge, UK: Cambridge University Press.
22. Schuster, P. (1977). The hypercycle: A principle of natural self-organization. Naturwissenschaften, 64,
541 – 565.
23. Varela, F. J., Maturana, H. R., & Uribe, R. (1974). Autopoiesis: The organization of living systems.
BioSystems, 5(4), 187 – 196.
24. von Neumann, J. (1966). Theory of self-reproducing automata. Bloomington, IL: University of Illinois Press.
l
D
o
w
N
o
UN
D
e
D
F
R
o
M
H
T
T
P
:
/
/
D
io
R
e
C
T
.
M
io
T
.
e
D
tu
UN
R
T
l
/
/
l
UN
R
T
io
C
e
–
P
D
F
/
/
/
/
1
4
3
2
4
5
1
6
6
2
5
1
4
UN
R
T
l
.
/
.
.
2
0
0
8
1
4
3
1
4
3
0
1
P
D
.
.
F
B
sì
G
tu
e
S
T
T
o
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
254
Artificial Life Volume 14, Numero 3
Scarica il pdf