Emergence of Self-Reproducing - 麻省理工学院人工智能研究专业

Emergence of Self-Reproducing
Metabolisms as Recursive
Algorithms in an Artiﬁcial
Chemistry

Abstract One of the main goals of Artiﬁcial Life is to research the
conditions for the emergence of life, not necessarily as it is, but as it
可能. Artiﬁcial chemistries are one of the most important tools
for this purpose because they provide us with a basic framework to
investigate under which conditions metabolisms capable of
reproducing themselves, 最终, of evolving, can emerge.
While there have been successful attempts at producing examples of
emergent self-reproducing metabolisms, the set of rules involved
remain too complex to shed much light on the underlying principles
at work. 在本文中, we hypothesize that the key property needed
for self-reproducing metabolisms to emerge is the existence of an
autocatalyzed subset of Turing-complete reactions. We validate this
hypothesis with a minimalistic artiﬁcial chemistry with conservation
法律, which is based on a Turing-complete rewriting system called
combinatory logic. Our experiments show that a single run of this
化学, starting from a tabula rasa state, discovers—with no
external intervention—a wide range of emergent structures
including ones that self-reproduce in each cycle. All of these
structures take the form of recursive algorithms that acquire basic
constituents from the environment and decompose them in a
process that is remarkably similar to biological metabolisms.

Germán Kruszewski*
Naver Labs Europe

germank@gmail.com

Tomáš Mikolov
Czech Institute of Informatics,

Robotics, and Cybernetics, Prague

Czech Technical University
tmikolov@gmail.com

关键词
Artiﬁcial chemistry, emergence,
self-reproduction, metabolisms, recursive
算法

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

1 介绍

One central area of focus for Artiﬁcial Life is characterizing the conditions that lead to the
emergence of living systems. 更确切地说, the goal
is to understand under which condi-
tions metabolisms capable of sustaining themselves in time, reproducing, 最终, evolving
can emerge. Artiﬁcial chemistries can be used to reveal this process by simulating the properties
of natural chemical systems at different levels of abstraction (see Dittrich et al., 2001, for a
thorough review). The driving hypothesis is that complex organizations emerge from the interac-
tions of simpler components thanks to self-organizing attractors in chemical networks (考夫曼,
1993; 沃克 & Ashby, 1966; Wuensche et al., 1992). While some artiﬁcial chemistries model as
closely as possible the properties of the chemistry that gave rise to life on Earth (Flamm et al., 2010;

* 通讯作者.

Artiﬁcial Life 27: 277–299 (2022) https://doi.org/10.1162/artl_a_00355

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

Högerl, 2010; Young & Neshatian, 2013), others leave out the particularities of natural chemistry
to focus only on their hypothesized core computational properties (Buliga & 考夫曼, 2014;
di Fenizio and Banzhaf, 2000; 丰塔纳 & Buss, 1994; Hutton, 2002; Sayama, 2018; Tominaga
等人。, 2007). 有趣的是, some of these studies have described systems that produce emer-
gent metabolic structures (Bagley & Farmer, 1992), and others feature self-reproducing structures
还有 (Hutton, 2002; Young & Neshatian, 2013), at times also capable of undergoing evolu-
的 (Hutton, 2007). 然而, it is still not clear which of the properties in these chemical sys-
tems are central to the emergence of these structures. 然而, gaining such insights is a crucial step
for deriving more general biological theories grounded both in life-as-it-is and life-as-it-might-be
(兰顿, 1989).

这里, we hypothesize that self-reproducing metabolisms emerge as a subset of autocatalyzed
reactions within a Turing-complete set. To validate this idea, we introduce combinatory chemistry, 一个
artiﬁcial chemistry designed to capture the core computational properties of living systems. It con-
sists in a set of autocatalyzed reactions that are based on the rewriting rules of combinatory logic (Curry
等人。, 1958; Schönﬁnkel, 1924). These reactions inherit from the original rewiring rules the capacity
to perform universal computation. 此外, we adapted the rules so that the ensuing reactions
would have conservative dynamics. Completing the set of possible reactions, there are random mix-
ing rules that act at a far lower rate.

The resulting chemical system is strongly constructive (Fontana et al., 1993), 意思是
that as the system evolves in time it can create—by chance or through the action of its own
components—new components that can in turn modify its global dynamics. 此外, thanks to
its universal computation capabilities, there is no theoretical limit to the complexity that emergent
forms can have. 另一方面, because of the conservation dynamics, the memory cost of
the system remains constant without needing to introduce external perturbations (such as randomly
removing elements from the system), while possibly also providing a natural source of selective
pressure.

In contrast to previous work that explicitly banned expressions that would not reduce to a normal
形式 (di Fenizio and Banzhaf, 2000; 丰塔纳 & Buss, 1994), combinatory chemistry can handle
them adequately by distributing their (potentially inﬁnite) computation steps over time as individual
reactions. 还, with respect to an earlier version of this work (Kruszewski & 米科洛夫, 2020), 这里
we have further simpliﬁed the system, dropping the “reactant assemblage” mechanism through
which we used to feed emergent structures with their required resources. This mechanism enabled
them to grow their activity and thus be more easily spotted, but it also biased the evolution of the
系统. 反而, here we have devised a new metric to identify these structures in naturally occurring
resource conditions. 而且, we use Gillespie’s algorithm (Gillespie, 1977) to simulate the time
evolution of the system to obtain unbiased samples of the proposed process, instead of the more
simplistic algorithm that was used before.

Starting from a tabula rasa state consisting of only elementary components, combinatory chem-
istry produces a diversity explosion, which then develops into a state dominated by self-organized
including recursively growing and
emergent autopoietic structures (Maturana & 瓦雷拉, 1973),
self-replicating ones. 尤其, all these types of structures emerge during a single run of the sys-
tem without requiring any external intervention. 此外, they preserve themselves in time by
absorbing compounds from their environment and decomposing them step by step, in a process
that has a striking resemblance to the metabolism of biological organisms. These structures take the
form of recursive algorithms that never reach a normal form (IE。, halting point) as long as sufﬁ-
cient resources are present in their environment. 尤其, we found that Turing-completeness was
required in combinatory chemistry for representing self-replicating structures, but not for simple
autopoietic or recursively growing ones.

This article is organized as follows. 第一的, we describe earlier work in artiﬁcial chemistry that is
most related to the approach introduced here. 然后, we explain the basic workings of combinatory
logic and how we adapted it in an artiﬁcial chemistry. 第三, following earlier work, we discuss how
autocatalytic sets can be used to detect emerging phenomena in this system, and propose a novel

278

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

measure of emergent complexity, which is well adapted to the introduced system. 最后, we de-
scribe our experiments showcasing the emergence of complex structures in combinatory chemistry
and discuss their implications.

2 Artiﬁcial Chemistries

Artiﬁcial chemistries are models inspired in natural chemical systems that are usually deﬁned by
three different components: a set of possible molecules, a set of reactions, and a reactor algorithm
describing the reaction vessel and how molecules interact with each other (Dittrich et al., 2001).
In the following discussion, we will focus on the algorithmic chemistries that are the closest to the
present work.

AlChemy (丰塔纳 & Buss, 1994) is an artiﬁcial chemistry where molecules are given by
λ-calculus expressions. λ-calculus is a mathematical formalism that, like Turing machines, can de-
scribe any computable function. In AlChemy, pairs of randomly sampled expressions are joined
through function application, evaluated, and the corresponding result is added back to the pop-
计算. To keep the population size bounded, expressions are randomly discarded. Fontana and
Buss showed that expressions that computed themselves quickly emerged in this system, 哪个
they called level 0 组织. 此外, when these expressions were explicitly prohibited, A
more complex organization emerged where every expression in a set was computed by other ex-
pressions within the same set (等级 1 组织). 最后, mixing level 1 organizations could
lead to higher order interactions between them (等级 2 组织). 然而, this system had some
局限性. 第一的, each level of organization was only reached after external interventions. 在广告中-
迪迪, programs were evaluated using β reductions, which require that they reach a normal
形式, 即, that there are no more λ-calculus rules than can be applied. 因此, recursive pro-
克, which never reach a normal form, are banned from the system. 这里, we use weak reduc-
tions instead, allowing the system to compute the time evolution of programs that never reach
a formal form. 有趣的是, it is exactly in this way that emergent metabolisms are represented.
此外, in AlChemy, two processes were introduced as analogues of food and waste, 关于-
spectively. 第一的, when expressions are combined, they are not removed from the system, allow-
ing the system to temporarily grow in size. 第二, expressions that after being combined with
existing expressions do not match any λ-calculus reduction rules are removed. Without these
流程, complex organizations fail to emerge. 然而, it is not clear under which circumstances
these external interventions would not be needed anymore in order for the system to evolve
autonomously. 最后, bounding the total number of expressions by randomly removing excess
ones creates perturbations to the system that can arbitrarily affect the dynamics. Fontana and
Buss (1996) later proposed MC2, a chemistry based on linear logic that addressed some of these
局限性 (尤其, conservation of mass), although we are not aware of empirical work on it.

这里, we propose an artiﬁcial chemistry based on combinatory logic. This formalism has been
explored before in the context of artiﬁcial chemistries by di Fenizio and Banzhaf (2000). This work
also introduces conservation laws, even though they rely on decomposing expressions to their in-
dividual components, introducing some randomness into the dynamics that here we have avoided.
此外, like AlChemy, it reduces expressions until they reach their normal forms, explicitly
forbidding recursive and other types of expressions that do not converge.

Other very related artiﬁcial chemistries are based on graph rewriting systems. Squirm3
(Hutton, 2002) is a chemistry in which atoms are placed in a 2D grid where they can react with
彼此, creating or breaking bonds. 有趣的是, Hutton (2002) shows that self-reproducing
evolvable chains can emerge in this environment when using the right set of reactions, which like
in the artiﬁcial chemistry here introduced, have intrinsic conservation laws. 然而, it remains un-
clear which characteristics of those reactions make it possible for this emergence to occur. 在
this work, we study the hypothesis that self-reproducing metabolisms are linked to recursive pro-
grams expressed through a network of autocatalysed reactions endowed with universal computation

Artiﬁcial Life Volume 27, Number 3–4

279

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

能力. In a different vein, Chemlambda (Buliga, 2020; Buliga & 考夫曼, 2014) is a Turing-
complete graph rewriting artiﬁcial chemistry that allows the encoding of λ-calculus and combina-
tory logic operators. 像这样, it is complementary in many ways to the system proposed here. 尽管
the original Chemlambda did not consider conservation laws, an extension called Hapax is currently
exploring them. 然而, emergent phenomena have not yet been explored under this formalism.

3 Combinatory Logic

Combinatory logic is a minimalistic computational system that was independently invented by
Moses Schönﬁnkel, John von Neumann, and Haskell Curry (Cardone & Hindley, 2006). Aside from
its relevance to Computability Theory, it has also been applied in Cognitive Science as a model for
a Language of Thought (匹安多糖, 2021). One of the main advantages of combinatory logic is its
formal simplicity while capturing Turing-complete expressiveness. In contrast to other mathemat-
ical formalisms, such as λ-calculus, it dispenses with the notion of variables and all the necessary
bookkeeping that comes with it. 例如, a function f (X)
y would be nonsensical,
and a function-generating system based on λ-calculus would need to have explicit rules to avoid
the formation of such expressions. 反而, combinatory logic expressions are built by composing
elementary operators called combinators. 这里, we restrict combinators to S, K and I, which form a
Turing-complete basis.1 A combinatory logic expression is deﬁned either to be a singleton combina-
tor or recursively, given two expressions x and y, by the application operation (x y). It is important to
note that, by convention, application is left-associative and thus, (x yz ) 和 ((x y)z ) are equivalent.
(αXβ) where X is a well-formed subexpression and α and
Given an expression e of the form e
β are some arbitrary left and right context, it can be rewritten in combinatory logic, as follows:

A(如果 )β ⊲ αfβ
A(Kfg)β ⊲ αfβ
A(Sfgx)β ⊲ α(fx(gx))β

什么时候 (αXβ) matches the left-hand side of any of the rules above, the term X is called a reducible
expression or redex. A single expression can contain multiple redexes. If no rule is matched, 前任-
pression is said to be in normal form. The application of these rules to rewrite any redex is called a
(weak) reduction. 例如, 表达方式 (SII(SII)) could be reduced as follows (underlining the
corresponding redexes being rewritten): (SII(SII)) ⊲ (我(SII)(我(SII))) ⊲ (SII(我(SII))) ⊲ (SII(SII)).
因此, this expression, also known as the omega combinator, reduces to itself. We will later see that
expressions such as this one will be important for the self-organizing behavior of the system intro-
duced here. 相比之下, (SII) is not reducible because S requires three arguments.2 Additionally,
note that (我(SII)(我(SII))) has two redexes that can be rewritten, 即, the outermost or the in-
nermost I combinators. Even though many different evaluation order strategies have been deﬁned
(Pierce, 2002), here we opt for picking a redex at random, both because this is more natural for
a chemical system and to avoid limitations that would come from following a ﬁxed deterministic
evaluation order.

4 Combinatory Chemistry

One of our main contributions deals with reformulating these reduction rules as reactions in a chem-
ical system with conservation laws. 为了这, we postulate the existence of a multiset of combinatory

1 事实上, S and K sufﬁce because I can be written as (SKK ). The inclusion of I simply allows for expressing more complex

programs with shorter expressions.

2 还, I cannot be reduced with I as an argument because (SII)

到 (和).

280

((和)我) 因此, the second I is not an argument for the ﬁrst I but

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

logic expressions P that react following reduction rules, plus random condensation and cleavages.
原则, the application of a reduction rule to any expression involves removing one copy of the
expression from the multiset and adding back the resulting product of the rule. Note that if we were
to apply plain combinatory logic rules to reduce these expressions, the total number of combinators
in the system would not be preserved (Lafont, 1997)—ﬁrst, because the application of a reduction
rule always removes the ﬁrst combinator in the redex from the resulting expression; 第二个,
because while the K combinator discards a part of the expression (the argument g), S duplicates its
third argument x. 因此, to make a chemical system with conservation laws, we posit that, on one
手, reduction operations can generate one or more by-product expressions. 另一方面,
the reduction rules can be applied to more than one expression simultaneously. 所以, using the
symbol to indicate that multiple expressions are being rewritten when it appears on the left-hand
+
边, or more than one expression is being added back to the multiset when it is on the right-hand
边, we deﬁne reduce reactions for an expression or substrate (αXβ), as follows:

A(如果 )β
A(Kfg)β

X
+
reactant

⇒
⇒
⇒

A(Sfgx)β

substrate

我
G

αfβ
+
αfβ
K
+
+
A( fx(gx))β

产品

+
by-product

(1)
(2)
(3)

|{z}

}

|
An expression in combinatory chemistry is said to be reducible if it contains a combinatory chem-
istry redex (CC-redex). A CC-redex is a plain combinatory logic redex, except when it involves the
reduction of an S combinator, in which case a copy of its third argument x (the reactant) must also
be present in the multiset P for it to be a redex in combinatory chemistry. 例如, the ex-
pression SII(SII) is reducible if and only if the third argument of the combinator S, 即 (SII), 是
also present in the set. When a reduction operation is applied, the redex is rewritten following the
rules of combinatory logic, removing any reactant from P and adding back to it the product and all
by-products, as speciﬁed on the right-hand side of the reaction. The type of combinator being reduced
gives name to the reaction. 例如, the S-reaction operating on SII(SII)
(SII) removes these
two elements from P, adding back I(SII)(我(SII)) and S to it. 尤其, each of these reduction rules
preserves the total number of combinators in the multiset, intrinsically enforcing conservation laws
in this chemistry. It is also worth noting that each of these combinators plays different roles in the
creation of novel compounds. While K-reactions split the expression, decreasing its total size and
复杂, S-reactions create larger and possibly more complex expressions from smaller parts.

In contrast to previous attempts in which expressions were combined and then reduced to nor-
mal form (di Fenizio and Banzhaf, 2000; 丰塔纳 & Buss, 1994)—thus being forced to exclude
expressions that did not reach a normal form—here each reduce reaction corresponds to a single
reduction step that can always be computed. 为此原因, we do not need to take any precau-
tions to avoid recursive expressions, but instead allow these interesting programs to form part of
our system’s dynamics.

Completing the set of possible reactions in this chemistry, condensations and cleavages can

generate novel expressions through random recombination:

←→

(xy)

(4)

Condensations correspond to the application operation between x and y, whereas cleavages are the
inverse. Note that cleaving (xyz) can only result in (xy)
z because, 否则, the tree structure
would not be preserved.

In combinatory chemistry, computation takes precedence. This means that reduction reactions
must happen at much higher rates than those of random recombination. Over the following section
we detail how this happens.

Artiﬁcial Life Volume 27, Number 3–4

281

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

4.1 Temporal Evolution
The system is initialized with a tabula rasa state containing only expressions with a single combinator
S, K, or I. 这样, we can be sure that any emergent diversity is the consequence of the system’s
dynamics rather than the outcome of an external intervention. 然后, it evolves by sampling reactions
following Gillespie’s algorithm (Gillespie, 1977, 2007). We note that the time evolution algorithm
has changed from an earlier version of this work (Kruszewski & 米科洛夫, 2020) in favor of this
more principled approach.

}

∈{

X,5

S,K,我

} ≫

更确切地说, we deﬁne a propensity function aj(X) for each reaction j, which computes the
unnormalized probability that the reaction j will occur within an inﬁnitesimal time interval given the
system’s state vector x. The component xx indicates the number of instances of an expression x
that are present in P. To deﬁne the propensity functions, we make use of reaction rate constants
kX, k5, kAS , kAK, kAI , for the cleavage, condensation, 和S, K, and I reduction reactions, 关于-
spectively. 重要的, because in combinatory chemistry computation takes precedence, reaction
rates kj of reduction reactions must be signiﬁcantly larger than those of random recombinations:
kA
. The propensity function takes different forms depending on whether the
reaction is unimolecular or bimolecular, following the formulation of Gillespie (2007). For uni-
molecular reactions, such as I and K reductions, and cleavages, aj takes the form aj(X)
cjxx1 where
=
xx1 is the number of copies of the reaction’s substrate x1 in x. For bimolecular reactions like S
reductions and condensation with substrate x1 and reactant x2, it takes the form aj(X)
cjxx1xx2
x2, where xx1 and xx2 are the number of
if x1 6=
=
expressions of x1 and x2, 分别. In the case of unimolecular reactions, cj is equal to a reaction
X, AK, 人工智能}
rate constant kJ where J
is the type of reaction j, whereas for bimolecular reactions
∈ {
x2 and 2kJ/(西德:127) if x1 =
x2, 在哪里 (西德:127) is the volume of the simulated container
kJ/(西德:127) if x1 6=
cj =
5, AS}
(Gillespie, 2007) 和 J
.
然后, the probability of the next reaction being j is p( j)

j aj(X), 和
the time interval until its occurrence is distributed as an exponential distribution with parameter a0.
To sample from this process, we follow the direct method (Gillespie, 1977). For efﬁciency reasons,
we factorize the reaction probability by the kind of the next reaction J being a condensation (5),
a cleavage (X ), or a reduction (A
stands for the set of all
possible Z reductions:

aj(X)/a0 where a0 =

x2 and the form aj(X)

2 xx1(xx1 −

1) if x1 =

人工智能), 在哪里

AZ}Z
{

AK ∪

AS ∪

S,K,我
}

∈ {

磷

∈{

西杰

p( j)

XJ
∈{

5,X,A
}

J)p( J),

p( j

(5)

where p( J)

aJ(X)/a0(X), a0(X)

J
∈{

5,X,A
}

aJ(X), and aJ =

J aj(X).

j
∈

For cleavage and condensation reactions, aJ takes a simpler form that can be efﬁciently computed
x xx, whereas for reduce reactions we must

by keeping track of the total number of expressions
explicitly sum over all of reactions:

磷

xS −

xK −

! -

X
X

aX(X)

a5(X)

aA(X)

k5
(西德:127)

人工智能
Xj
∈

X
X
kIxj1 +

Xx ′

AK
Xj
∈

xx ′ −

1
!

kKxj1 +

AS
Xj
∈

kS
(西德:127)

xj1xj2 ,

磷

(6)

(7)

(8)

where j1 is the substrate of the reduction reaction j and j2 is the reactant in the case of reducing an
S combinator.

282

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

因此, to sample a reaction, we ﬁrst sample the reaction type J. If it is a cleavage, then we sample
one expression according to its concentration, and cleave it into two subexpressions by dividing it
at the root. If it is a condensation, then we sample two expressions according to their concentration
(第二, after removing one element of the ﬁrst one), and combine them through the application
操作员. 最后, if it is a reduction, then we sample one reduce reaction from the space of all
possible reduce reactions, with probability proportional to its propensity. 在实践中, we just need to
compute all possible reductions involving the expressions that are present in the system’s state.3 The
complete algorithm describing the temporal evolution of our system is summarized on Algorithm 1.4

Algorithm 1. Time evolution algorithm

输入: Num. of combinators NI, NK, NS; Reaction rates kX, k5, kA
Initialize multiset P
Initialize time t
0

我 : NI, K : NK, S : NS}}

← {{

while True do

←

磷

←

X
Compute aX(X), a5(X), aA(X), and a0(X) following Equations 6-8
aJ(X)/a0(X)
Sample reaction type J

with prob. p( J)

X, 5, A
}

∈ {

if J

X then // cleave

=
Sample expr. x w/prob. p(X)
x1 +

x2] where x
→
5 然后 // condense

←
else if J

>1]kXxx
1[
X
|
|
aX(X)

(x1x2)

Sample expr. x1 w/prob. p(X)

←
else if J

[x1 +
=

Sample expr. x2 w/prob. p(X)
x2 →

(x1x2)]

A then // reduce
Sample reaction j w/prob. p(j)
=
xj1 + 1

aj(X)

人工智能

xx/
1[X

x xx
x1](xx
(

磷
=

1)
-
x xx

+ 1[X
1)
-

x1]xx

磷

aj(X)/aA(X) 在哪里

(西德:2)

(西德:0)

∈

∈{

=
S,K,我
}
Let x1, . . . , xn, y1, . . . , ym s.t. j
磷

xj1 + 1
are all Z reductions following Rules 1–3
(西德:3)
(西德:3)
(西德:2)
(西德:2)
y1 + ··· +
xn →
x1 + ··· +
=
n
X : xx −
做]
希]
1 1[ X
我
}}
=
+
=
1
1) where u
0 (X) ln(u−
a−

米
1 1[ X
我
=
U(0, 1)
磷

← {{
t

磷

∈

(西德:3)

←

～

xj1 xj2

和

(西德:1)

5 Emergent Structures

Having described the dynamics of combinatory chemistry, we now turn to discuss how we can
characterize emergent structures in this system. 为了这, we ﬁrst discuss how autocatalytic sets can
be applied for this purpose. 第二, we observe that this formalism may not completely account for

3 Some expressions can participate in a very large number of reductions, considerably slowing the simulation. 为此原因, 这

system is currently limited to computing up to 10 reductions per expression in no special order.

4 We make available the code to simulate combinatory chemistry in https://github.com/germank/combinatory-chemistry.

Artiﬁcial Life Volume 27, Number 3–4

283

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

some emergent structures of interest, 因此, we propose to instead track reactant consumption
rates as a proxy metric to uncover the presence of these structures. 最后, we enrich this metric to
detect consumption levels that are above chance levels.

5.1 Autocatalytic Sets
Self-organized order in complex systems is hypothesized to be driven by the existence of attracting
states in the system’s dynamics (考夫曼, 1993; 沃克 & Ashby, 1966; Wuensche et al., 1992).
Autocatalytic sets (考夫曼, 1993) were ﬁrst introduced by Stuart Kauffman in 1971 as one type
of such attractors that could help explain the emergence of life in chemical networks. (See Hordijk,
2019, for a comprehensive historical review on the topic.) Related notions are the concept of au-
topoiesis (Maturana & 瓦雷拉, 1973), and the hypercycle model (Eigen & Schuster, 1978).

Autocatalytic sets are reaction networks that perpetuate in time by relying on a network of catalyzed
reactions, where each reactant and catalyst of a reaction is either produced by at least some reaction
in the network, or it is freely available in the environment. This notion was later formalized in
mathematical form (Hordijk & Steel, 2004; Hordijk et al., 2015) with the name of reﬂexively autocatalytic
food-generated sets (RAFs). Particularly, a chemical reaction system (CRS) is ﬁrst deﬁned to denote the set
of possible molecules, the set of possible reactions, and a catalysis set indicating which reactions are
catalyzed by which molecules. 此外, a set of freely available molecules in the environment,
called the food set, is assumed to exist. 然后, an autocatalytic set (or RAF set) S of a CRS with
associated food set F is a subset of reactions, 这是:

1. reﬂexively autocatalytic (RA): Each reaction r

S is catalyzed by at least one molecule that is

∈
either present in F or can be formed from F by using a series of reactions in S itself.

2. food-generated (F): Each reactant of each reaction in S is either present in F or can be formed

by using a series of reactions from S itself.

5.2 Metabolic Structures in Combinatory Chemistry
In combinatory chemistry, all reducing reactions take precedence over random condensations and
cleavages, 因此, they proceed at a higher rate than random reactions without requiring deﬁnition
of a catalyst. 所以, we say that they are autocatalyzed and note that they all trivially satisfy con-
迪迪 1. 因此, autocatalytic sets in this system are deﬁned in terms of subsets of reduce reactions
in which every reactant is produced by a reduce reaction in the set or is freely available in the envi-
(SII) is in the food set, 数字 1 节目
罗门特 (状况 2). 例如, if we assume that A
(SII(SII)). As shown, a chain of
a simple autocatalytic set associated with the expression (AA)
reduce reactions keeps the expression in a self-sustaining loop: When the formula is ﬁrst reduced
by the reaction r1, a reactant A is absorbed from the environment and one S combinator is released.
Over the following steps, two I combinators are sequentially applied and released back into the
multiset P, with the expression returning back to its original form. 换句话说, in one cycle the
expression (AA) absorbs one copy of A from the environment releasing back into it the elementary
components obtained as by-products of the reactions. We refer to this process as a metabolic cycle

数字 1. r1–r5 form an autocatalytic set, granted that (SII) belongs to the food set. (SII(SII))’s metabolic cycle starts
with r1 reducing the S combinator, while taking (SII) as reactant. 然后, the cycle is completed by the reduction of the
two identity combinators, in any of the possible orders. Original ﬁgure from Kruszewski & 米科洛夫, 2020, used with
permission.

284

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

数字 2. One of the possible pathways in the reduction of the tail-recursive structure (AA) with A
(S(和)我). 它
appends one A to itself by metabolizing another copy absorbed from the environment. Original ﬁgure from Kruszewski
& 米科洛夫, 2020, used with permission.

nKK

⇒∗ (AA)

because of its strong resemblance to its natural counterpart. 为了方便, we write the just de-
scribed cycle as (AA)
φ(A), where φ is a convenience function that allows us to
succinctly represent the decomposition of A as elementary combinators by mapping its argument
nII where nS, nK, and nI stand for the number of S, K, and I combinators in A,
into nSS
+
和
⇒∗ symbol indicates that there exists a pathway of reduction reactions from the reactives
in the left-hand side to the products in the right-hand side.
It should be noted that there are (inﬁnitely) many possible pathways, some of them not neces-
sarily closing the loop. 例如, instead of reducing (SII(我(SII))) through the only available I
reduction (r4 in Figure 1), it could also be possible to reduce the full expression by applying the S
reduction rule as long as at least one copy of (我(SII)) is present in P, yielding (我(我(SII))(我(我(SII))))
因此. We could continue reducing this expression, ﬁrst through the two outermost I combina-
托尔斯, thus obtaining (SII(我(我(SII)))), and then though the ﬁrst S combinator, provided that a copy
的 (我(我(SII))) is present in P, obtaining (我(我(我(SII)))(我(我(我(SII))))) 因此. This outermost-ﬁrst
reduction order could be followed ad inﬁnitum, stacking ever more I combinators within the ex-
压力. 尽管如此, this also has a cost, as there must be copies of reactants (我(SII)), (我(我(SII))),
. . . , (我(. . . (我(SII)))) in the multiset P for these reactions to occur, and longer expressions are nor-
mally scarcer. 为此原因, when we talk about the metabolic cycle we usually refer to the least
effort cycle, in which I and K combinators are reduced before S ones, and where S combinators
with shorter or naturally more frequent expressions in the third argument (the reactant) are reduced
before longer ones.

While autocatalytic sets provide a compelling formalism to study emergent organization in ar-
tiﬁcial chemistry, they also leave some blind spots for detecting emergent structures of interest.
(S(和)我(S(和)我)).
Such is the case for recursively growing metabolisms. 考虑, 例如, e
(S(和)我) applied to itself (AA). As shown
This expression is composed of two copies of A
图中 2, during its metabolic cycle, it will consume two copies of the element A, metab-
olizing one to perform its computation and appending the other one to itself, 因此 (AA)
+
φ(A). As time proceeds, the same computation will occur recursively, 因此
2A
(A(AA))
φ(A), 等等. While this particular behavior cannot be
detected through autocatalytic sets, because the resulting expression is not exactly equal to the orig-
inal one, it still involves a structure that preserves in time its functionality.

⇒∗ (A(AA))
2A
+

+
⇒∗ (A(A(AA)))

而且, while the concept of autocatalytic set captures both patterns that perpetuate them-
selves in time and patterns that also multiply their numbers, it does not explicitly differentiate
φ(A) (如
它们之间. A pattern with a metabolic cycle of the form AA
数字 1) keeps its own structure in time by metabolizing one A in the food set, but it does
not self-reproduce. We call such patterns simple autopoietic (Maturana & 瓦雷拉, 1973). 相比之下,
for a pattern to be self-reproducing it must create copies of itself that are later released as new ex-
pressions in the environment. 例如, consider a metabolic cycle in Figure 3 with the form

⇒∗ AA

Artiﬁcial Life Volume 27, Number 3–4

285

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

数字 3. Metabolic cycle (showing one of the possible pathways) of a self-reproducing structure that emerges from
the dynamics of combinatory chemistry. Starting from (AA), where A
(和(S(SK)我)), it acquires three copies of A from
its environment and uses two to create a copy of itself, metabolizing the third one to carry out the process. Original
ﬁgure from Kruszewski & 米科洛夫, 2020, used with permission.

(AA)
units of A and metabolizes a third one to carry out the process.

⇒∗ 2(AA)

φ(A). This structure creates a copy of itself from two freely available

5.3 Metrics for Detecting Emergence
All structures identiﬁed in the previous section have in common the need to absorb reactants from
the environment to preserve themselves in homeostasis. 此外, because they follow a cyclical
过程, they will continuously consume the same types of reactants. 因此, we propose tracking
reactant consumption as a proxy metric for the emergence of structures. 换句话说, we note that the
only operation that allows an expression to incorporate a reactant into its own body is the reduction
of the S combinator, and thus we count the number of reactants x consumed by expressions of the
δ) normalized by the total number of reactants consumed
form α(Sfgx)β in the time interval [t : t
in the same interval, denoting it as Ot:t

+
δ(X), or simply O(X).
的确, this metric was used in a previous version of this work (Kruszewski & 米科洛夫, 2020)
to detect emergent structures. 然而, it has the problem that it is also sensitive to reactants that are
consumed at high rates just because they are very frequent, and as a consequence, expressions
containing them as a third argument to an S combinator are expected to be common as well, inﬂating
this metric for uninteresting reactions.

为此原因, we propose measuring the (积极的) pointwise information.5 I(X) associated with
observing a consumption rate O(X) for a reactant x in contrast to its consumption rate if the process
were driven by chance only, 右(X):

我(X) def
=

max

日志

(西德:18)

氧(X)
右(X)

, 0

(西德:19)

(9)

We deﬁne R(X) as the relative frequency of any expression on a hypothetical process where no
reduce reactions are present, but instead only random mixing given by random collisions and

5 The name and the formula are related to the pointwise mutual information (采购经理人指数) metric (教会 & Hanks, 1990) that has been
extensively used in computational linguistics. PMI computes the log ratio between the empirical co-occurrence probability of two
events x and y with respect to their expected probability if these two events were independent, as given by the product of the
marginals. Like PMI, the proposed metric computes the log ratio between observed odds and chance-driven ones.

286

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

cleavages. To model this process, we follow the formulation of the reaction kinetic equations given
by Fellermann et al. (2017):

dxx
dt =

cX
c0

xz −

y,z
X
(yz)
X
=

y,z
X
(xy)
z
=
(yx)
z
=



















c5
c0

xyxz −

xxxy



(10)

y,z
X
(yz)
X
=






在哪里, cX =
normalized equilibrium concentration x∗x of expression x under these random kinetics:

k5/(西德:127), and c0 =

y,z
X
(xy)
z
=
(yx)
z
=

kX, c5







a0(X) is the partition function, and deﬁne R(X) 作为

右(X) def
=

x∗x
x x∗x

At equilibrium, 方程 10 admits the following solution:

磷

x∗x =

cX
c5

X
乙
e−
|

(11)

(12)

is the length of expression x and b is a constant that depends on the boundary conditions.
在哪里
尤其, we ask for the initial mass of the system, represented by the dimensionless constant M,
to be conserved in the equilibrium distribution by equating it to the total number of combinators:

x∗x|

| =

中号.

(13)

X
X
We can rewrite this equation by ﬁrst substituting x∗x according to Equation 12, and then replacing
the sum over expressions by a sum over lengths. Noting that there are knCn
1 expressions of length
-
n, where k
3 is the number of different possible combinators and Cn is the nth Catalan number,
=
this equation becomes:

cX
c5

∞

Xn
1
=

knCn
-

1e−

bnn

中号.

(14)

After solving this equation for b, we obtain b

日志

pute the normalization constant for the distribution x∗:

cX
c5

1
4M2

(西德:16)

(西德:17)

. 最后, we com-

∞

x∗x =

cX
c5

knCn
-

1e−

cX
2c5

乙
4ke−

(15)

Xn
1
=

X
X
completing the deﬁniton of I(X). We refer to Appendix 1 for all the computations verifying these
索赔. In the following section, we show its effects experimentally.

(西德:16)

(西德:17)

Artiﬁcial Life Volume 27, Number 3–4

287

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

6 Experiments and Discussion

(西德:1)

(西德:0)

6.1 指标
We began by testing the effect of the proposed information metric on a system with uniformly
104 S, K, and I combinators simulated until it reached time T
distributed M
1, 000. Candi-
date reactions are sampled by 10 threads working simultaneously. For all our experiments, 我们
used k5
中号. 我们
leave a thorough exploration of parameter values for future work. With these parameters, 这
expressions associated with random kinetic dynamics become b
1
2 (3
+
time t with those in the interval [ t

=
|. All curves are smoothed through locally averaging every data point at

106 and ﬁxed the dimensionless constant (西德:127)

104, kS =

=
kX =

1, kK =

和R(X)

kI =

√5)k

√5)

10, t

X
-|

10].

日志

(西德:0)

(西德:1)

We ﬁrst present the raw consumption rates O(X), which are displayed in Figure 4(A). As shown,
some of the most frequently consumed reactants include the atomic combinators S, K, 和我, 和
some of their binary compositions. Binary reactants such as (KI) and atomic ones such as I do not
form part of any stable structure, and the expressions consuming them are produced by chance.
然而, they are used with considerable frequency because S combinators are more likely to be ap-
plied to shorter arguments than longer ones. 为此原因, the consumption of I is considerably
higher than the consumption of (KI). 然而, even though by the same argument the consumption rate
(SII) should be below binary reactants, self-organization into autopoietic patterns drives
of A
the usage of this reactant above what would be expected if chance were the only force at play.
(SII) is associated with
的确, the curve corresponding to the consumption of the reactant A
the autopoietic pattern (SII(SII)), composed of two copies of this reactant, and a metabolic cycle
of the form (AA)
φ(A), 如图 1. 尽管如此, (S(和)我), used by
the structure in Figure 2, is cramped at the bottom with the binary reactants in the consumption
rate plot.

⇒∗ (AA)

When applying the proposed information metric I(X) the curves corresponding to emerging
structures become featured at the top of the graph whereas all other reactants that are mostly driven
by random generation are pushed to the bottom, 如图 4(乙). 所以, this experiment
showcases the usefulness of this metric in separating consumption rates propelled by emergent
structures from uninteresting fortuitous ones.

6.2 Emergent Metabolic Structures
For the next part, we studied some of the emergent structures in a system initialized with a tabula
106 evenly distributed S, K, and I combinators simulated for 1,000 units
rasa state consisting of M
时间的.

数字 4. Reactant consumption metrics for the most consumed reactants x in a simulation with 10k combinators.

288

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

In an earlier version of this work (Kruszewski & 米科洛夫, 2020), we had used a supplementary
mechanism called reactant assemblage, through which we “fed” emerging structures with their required
reactants to allow them to be spotted through sheer reactant consumption rates in a relatively small
system with only 10,000 combinators. 这里, we simpliﬁed the model and dropped the need for this
机制, thanks both to simulating a larger system with 1M combinators and to the usage of the
re-weighting metric presented in Metrics for Detecting Emergence, 多于, which allowed us to spot
emergent complex structures even at very low levels of reactant consumption rates.

We began by analyzing some general metrics on one given run of the system. 第一的, 并在
agreement with previous work (Meyer et al., 2009), we ﬁnd that there is a tendency for the system
to create increasingly longer expressions, as shown by the length of the largest expression in the
系统 (数字 5(A)). We also count the number of distinct expressions present in the system at any
given time, which we display in Figure 5(乙). As can be seen, diversity explodes at the beginning,
driven by the random recombination of the elementary combinators, peaking very early on, 然后
decreasing fast at ﬁrst, and then slower after about time 200. This behavior is consistent with a
system that self-organizes into attracting states dominated by fewer, but more frequent expressions.
再次, this result agrees with previous work that has shown that diversity decreases over time on a
number of ACs (Banzhaf et al., 1996; Dittrich & 班扎夫, 1998; Dittrich et al., 2001). 然而, 我们
note that in contrast with many of these systems that were initialized with random elements, 因此,
maximizing diversity from the start, here the initial diversity is an emergent property of the system
dynamics as it is only initialized with three different elements, 即, the singleton expressions S,
K, 和我. 下一个, we note that the proportion of reducing vs. random recombination reactions is an
emergent property of the system which depends on the number of reducible expressions that are
present in its state at any given time. As can be seen in Figure 5(C), this rate, which necessarily starts
在 0, increases sharply in the beginning, reaching slightly more than 30%. 然后, it starts to slowly
减少, but remains always above 25% during the studied period.

然而, it is unclear from these results whether there are emergent complex structures that act
as attractors, or if a different explanation for these outcomes is at play. To answer this question,
we turned to the reactant consumption rates weighted by Equation 9 to detect whether speciﬁc
reactants were more prominently used by some emergent structures.

Results are shown in Figure 6(A) for a few selected reactants that highlight the emergence of
different types of structures, including simple autopoietic, recursively growing, and self-reproducing
那些. 有趣的是, they can emerge at different points in time, co-exist, or be driven to extinction.
In parallel, 数字 6(乙) shows the number of copies of these reactants available at each discrete time
interval of unit length.

While there are (inﬁnitely) many possible expressions that can consume a given type of reac-
坦特, only a few of them will correspond to emergent metabolisms. 一般来说, we observed that
expressions that consume any given reactant A are typically composed of multiple juxtaposed copies

数字 5. Global metrics for a system initialized with 1M uniformly distributed S, K, and I combinators.

Artiﬁcial Life Volume 27, Number 3–4

289

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

数字 6. Simulation results for 1M uniformly selected S, K, and I combinators for 1, 000 几代人, on a set of
manually chosen reactants.

of this reactant in an expression of the form (AA). This is linked to the fact that in order to express
recursive functions in combinatory logic, the function (in this case denoted by A) must take itself
as its own argument, but this particularity also conﬁrms the old adage: “Tell me what you eat and I
will tell you what you are.”

The ﬁrst curve in Figure 6(A) (in the order of the legend) corresponds to the reactant A

(SII),
associated with the simple autopoietic structure of Figure 1. The consumption rates are much more
stabilized in comparison with the results reported in (乙), which belonged to a system that was 100
times smaller. 此外, the number of copies of this reactant decreases sharply at the beginning,
but then, intriguingly, they slowly increase again until reaching a concentration of about 200 units
in total.

The second reactant in the plot, (AA) (where A

(SII)) is not actually consumed by a
metabolism. 反而, it is consumed by one of the two possible reductions of the expression
(SII(SII)(SII(SII))). This new struc-
(A(AA))
(SII(SII)) 那
ture is yet another autopoietic structure that is composed of two copies of (AA)
persist in time by consuming the (SII) reactant independently of each other.

(SII(SII(SII))), which reduces to (AA(AA))

The next three reactants in Figure 6(A) correspond to recursively growing structures. 第一个
(S(和)我) and follows a right-branching cycle that linearly increases the
φ(A) (数字 2). The second one, with re-

(S(SII)我), also grows recursively, although with a left-branching structure: (AA)

φ(A). 第三, there is the reactant A

+
(S(SSI)K), which is associated with a

one uses the reactant A
size of the structure: (AA)
actant A
2A
+
binary-branching recursive structure.6

=
⇒∗ (AAA)
最后, the curve of the reactant A

(和(S(SK)我)) corresponds to the emergence of a
φ(A), thus dupli-
self-reproducing structure, following a cycle of the form (AA)
⇒∗ 2(AA)
cating itself after metabolizing one copy of the reactant in the process. 有趣的是, this structure
emerges not only through the effect of random recombination, but also thanks to self-organization.
Instead of being a product of a random combination of two copies of the reactant A, it of-
ten emerges after the condensation of other reactants, 例如 (S(和(和))(和)) 和 (S(SK)我),
(和(和(和))) 和 (S(SK)我), 或者 (SII) 和 (和(S(SK)我)), among other possibilities that induce a chain
of reduction reactions that result in producing at least one copy of (AA).

It is worth noting that one cycle of this structure’s metabolism requires three copies of the re-
actant. When there are none in the environment, the structure cannot proceed with its metabolism
and this structure is vulnerable to being cleaved or being condensed with an expression that will

6 See Appendix 2 for more details on these derivations.

290

Artiﬁcial Life Volume 27, Number 3–4

⇒∗ (A(AA))

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

cause it to stop functioning normally. Because of the rare supply of its six-combinator-long reac-
坦特, plus the fact that all existing structures compete with one another, the structure will fall into
extinction at about time t
400, when only
two reproduction cycles are completed, before falling back into oblivion. 尽管如此, we speculate
that in larger systems the population will recover from periods of resource scarcity by following the
periodic dynamics originally proposed by Lotka (1910), thus allowing these structures to perpetuate
in time.

200, although it will make a short comeback at time t

尤其, recursive structures also experience low resource conditions starting at time t

200.
然而, they might be able to cope with conditions of low resources more effectively because
their repetitive structure allows them to be cleaved and still conserve their function. 例如,
A(AA)
(AA) still leaves a functioning (AA) 结构. When new copies of A become
available either through the random condensation of combinators released by every computed re-
duction or by some other process, they can consume them and grow back again.

⇒

6.3 Other Bases
到目前为止, we have explored emergent structures on systems composed of S, K, and I combina-
托尔斯. Because one of the main goals of this work is linking the emergence of metabolic struc-
tures to the core computational properties of the underlying chemistry, we explored other possible
(较小) bases.

First of all, we note that using K or I combinators by themselves would not produce any
meaningful structure, neither would a combination thereof. Any expression formed out of these
combinators can only decay into binary expressions at most. In the case of the S combinator,
while it still allows expressions that can be reduced inﬁnitely, 例如 (SSS(SSS)(SSS)), 那里
are no expressions that do so by continually consuming the same reactant. 这是因为, 作为
shown by Waldmann (2000), there are no expressions X composed only of the S combinator such
⇒∗ (αXβ). 所以, autocatalytic sets are not possible in this environment. For all of
that X
these reasons, it is not meaningful to look at simulations containing either one of the S, K, or I
combinators alone.

The only two possible remaining subsets of combinators are the pairs S

K, 仅与
the latter being Turing-complete. We ran again experiments in which only one pair of combinators
was present. We used 104 combinators for the S
K one. 数字 7(A)
-
shows the information traces for the reactant (SII), consumed by the simple autopoietic structure
图中 1, 和 (S(和)我), consumed by the structure in Figure 2, corroborating that these struc-
tures also emerge when only S and I combinators are present. 图中 7(乙), we also note that
K basis, as shown by the consumption of
a homologous autopoietic structure emerges with S
the reactant A
⇒∗

(S(SK)(SKK)). This structure has a metabolic cycle of the form (AA)

-
I basis, 和 106 for the S

I and S

数字 7. Pointwise information for a selected set of reactants on different combinator bases.

Artiﬁcial Life Volume 27, Number 3–4

291

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

K base, as shown by the consumption of A

(AA)
φ(A), thus needing to absorb two extra copies of the reactant to perform the com-
putation, even if they are later released unchanged. 此外, recursively growing structures can
(S(SSK)), which is associated
be spotted in the S
with a metabolic cycle of the form (AAA)
AA,
4S
thus growing and incorporating SSK as a preﬁx in the process. 有趣的是, AA is absorbed and
released intact, which could be construed as an emergent catalyst for the reaction: Even though we
can interpret each reduce reaction to be autocatalyzed, reaction chains can have emergent proper-
领带, such as in this case, where a reactant is just used to complete the metabolic cycle and then
released.

⇒∗ (SSKA(AAA))

最后, we note that while we have not yet witnessed an emergent self-reproducing struc-

K only, it can in fact be represented with the expression (AA) where A
5S

ture using the S
=
(S(SK)(S(SK)(SKK))), and having as metabolic cycle (AA)
+
3K. 然而, ﬁnding it requires discovering a considerably longer expression than the one in the
SKI basis and consumes much longer reactants, which might explain why we have not yet found
them to emerge in our simulations at the current scale. 尽管如此, it is worth noting that in the
I basis it would not be possible to represent a self-reproducing metabolic cycle of
incomplete S
. . . for any X because this would ask for a reaction capable of producing as
the form X
a by-product an arbitrarily long expression that reduces to X at some point during the cycle. 然而,
S and I combinators have only themselves as by-products of their respective reactions and cannot
fulﬁll this requisite.

⇒∗ 2(AA)

-
⇒∗ 2X

7 结论

We have introduced combinatory chemistry, an algorithmic artiﬁcial chemistry based on combina-
tory logic. Even though it has relatively simple dynamics, it gives rise to a wide range of autopoietic
结构, including recursively growing and self-reproducing ones. These structures feature re-
action cycles that bear a striking resemblance to natural metabolisms. All of them take the form
of recursive algorithms that continually consume speciﬁc resources, incorporating them into their
structure and decomposing them to perform their function. Thanks to combinatory logic being
Turing-complete, the presented system can theoretically represent patterns of arbitrary complexity.
此外, we have argued that in the context of the SKI basis, this computational universality
property is both necessary and sufﬁcient to represent self-reproducing patterns, while also showing
them to emerge at least in the case where all three combinators are present. 另一方面, A
non-universal basis consisting only of S and I combinators can still give rise to simple autopoietic
and recursively growing structures.

The proposed system does not need to start from a random set of initial expressions to kick-start
diversity. 反而, this initial diversity is the product of the system’s own dynamics, as it is only
initialized with elementary combinators. 这样, we can expect that this ﬁrst burst of diversity
is not just a one-off event, but it is deeply embedded into the mechanics of the system, possibly
allowing it to keep on developing novel structures continually.

To conclude, we have introduced a simple model of emergent complexity in which
self-reproduction emerges autonomously from the system’s own dynamics. 将来, 我们将
seek to apply it to explain the emergence of evolvability, one of the central questions in Artiﬁ-
cial Life. We believe that the simplicity of the model, along with the encouraging results presently
obtained and the creativity obtained from balancing computation with random recombination to
search for new forms, leaves it in good standing to tackle the many challenges that lie ahead.

致谢
We would like to thank the two anonymous reviewers for their thorough and insightful feedback,
which signiﬁcantly improved earlier versions of this work.

292

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

参考
Bagley, 右. J。, & Farmer, J. D. (1992). Spontaneous emergence of a metabolism. 在C中. G. 兰顿, C. 泰勒,
J. D. Farmer, & S. 拉斯穆森 (编辑。), Artiﬁcial Life II: Proceedings of the interdisciplinary workshop on the synthesis
and simulation of living systems (PP. 93–140). Addison-Wesley.

班扎夫, W., Dittrich, P。, & Rauhe, H. (1996). Emergent computation by catalytic reactions. Nanotechnology,

7(4), 307–314. https://doi.org/10.1088/0957-4484/7/4/001

Buliga, 中号. (2020). Artiﬁcial chemistry experiments with chemlambda, lambda calculus, 相互作用

combinators. ArXiv. https://arxiv.org/abs/2003.14332

Buliga, M。, & 考夫曼, L. (2014). Chemlambda, universality and self-multiplication. 在诉讼程序中

ALIFE 14: The fourteenth international conference on the synthesis and simulation of living systems (PP. 490–497). 和
按. https://direct.mit.edu/isal/proceedings-pdf/alife2014/26/490/1901863/978-0-262-32621-6
-ch079.pdf

Cardone, F。, & Hindley, J. 右. (2006). Lambda-calculus and combinators in the 20th century. 在D中. 中号. Gabbay

& J. 伍兹 (编辑。), Logic from Russell to Church (卷. 5, Handbook of the History of Logic, PP. 723–817).
爱思唯尔. https://doi.org/10.1016/S1874-5857(09)70018-4

教会, K. W., & Hanks, 磷. (1990). 词语关联规范, mutual information, 和词典编纂.

计算语言学, 16(1), 22–29.

Curry, H. B., Feys, R。, Craig, W., Hindley, J. R。, & Seldin, J. 磷. (1958). Combinatory logic (卷. 1). North-Holland

出版.

戴维斯, 时间. (2006). Catalan numbers. https://mathcircle.berkeley.edu/sites/default/ﬁles/BMC6/pdf0607

/catalan.pdf

di Fenizio, 磷. S。, & 班扎夫, 瓦. (2000). A less abstract artiﬁcial chemistry. 在米. A. 巴杜, J. S. McCaskill,
氮. H. 帕卡德, & S. 拉斯穆森 (编辑。), Artiﬁcial Life VII: Proceedings of the seventh international conference on
Artiﬁcial Life (PP. 49–53). 与新闻界.

Dittrich, P。, & 班扎夫, 瓦. (1998). Self-evolution in a constructive binary string system. Artiﬁcial Life, 4(2),

203–220. https://doi.org/10.1162/106454698568521, 考研: 9847424

Dittrich, P。, Ziegler, J。, & 班扎夫, 瓦. (2001). Artiﬁcial chemistries: A review. Artiﬁcial Life, 7(3), 225–275.

https://doi.org/10.1162/106454601753238636, 考研: 11712956

Eigen, M。, & Schuster, 磷. (1978). The hypercycle. Naturwissenschaften, 65(1), 7–41. https://doi.org/10.1007

/BF00420631

Fellermann, H。, Tanaka, S。, & 拉斯穆森, S. (2017). Sequence selection by dynamical symmetry breaking in
an autocatalytic binary polymer model. Physical Review E, 96(6), 文章 062407. https://doi.org/10.1103
/PhysRevE.96.062407, 考研: 29347334

Flamm, C。, Ullrich, A。, Ekker, H。, Mann, M。, Högerl, D ., Rohrschneider, M。, Sauer, S。, Scheuermann, G。,

Klemm, K., Hofacker, 我. L。, & Stadler, 磷. F. (2010). Evolution of metabolic networks: A computational
frame-work. Journal of Systems Chemistry, 1(1), 文章 4. https://doi.org/10.1186/1759-2208-1-4

丰塔纳, W., & Buss, L. 瓦. (1994). What would be conserved if “the tape were played twice”? 诉讼程序
美国国家科学院, 91(2), 757–761. https://doi.org/10.1073/pnas.91.2.757, 考研: 8290596

丰塔纳, W., & Buss, L. 瓦. (1996). The barrier of objects: From dynamical systems to bounded

组织. 在J. Casti & A. Karlqvist (编辑。), Boundaries and barriers (PP. 56–116). Addison-Wesley.

丰塔纳, W., 瓦格纳, G。, & Buss, L. 瓦. (1993). Beyond digital naturalism. Artiﬁcial Life, 1(1–2), 211–227.

https://doi.org/10.1162/artl.1993.1.1_2.211

Gillespie, D. 时间. (1977). Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry,

81(25), 2340–2361. https://doi.org/10.1021/j100540a008

Gillespie, D. 时间. (2007). Stochastic simulation of chemical kinetics. Annual Review of Physical Chemistry, 58,

35–55. https://doi.org/10.1146/annurev.physchem.58.032806.104637, 考研: 17037977

Högerl, D. (2010). Simulation of prebiotic chemistries (Master’s thesis). 维也纳大学.

Hordijk, 瓦. (2019). A history of autocatalytic sets: A tribute to Stuart Kauffman. Biological Theory, 14(4),

224–246. https://doi.org/10.1007/s13752-019-00330-w

Hordijk, W., 史密斯, J. 我。, & Steel, 中号. (2015). Algorithms for detecting and analysing autocatalytic sets.

Algorithms for Molecular Biology, 10(1), 文章 15. https://doi.org/10.1186/s13015-015-0042-8, 考研:
25969692

Artiﬁcial Life Volume 27, Number 3–4

293

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

Hordijk, W., & Steel, 中号. (2004). Detecting autocatalytic, self-sustaining sets in chemical reaction systems.
理论生物学杂志, 227(4), 451–461. https://doi.org/10.1016/j.jtbi.2003.11.020, 考研:
15038982

Hutton, 时间. J. (2002). Evolvable self-replicating molecules in an artiﬁcial chemistry. Artiﬁcial life, 8(4), 341–356.

https://doi.org/10.1162/106454602321202417, 考研: 12650644

Hutton, 时间. J. (2007). Evolvable self-reproducing cells in a two-dimensional artiﬁcial chemistry. Artiﬁcial Life,

13(1), 11–30. https://doi.org/10.1162/artl.2007.13.1.11, 考研: 17204010

考夫曼, S. A. (1993). The origins of order: Self-organization and selection in evolution. 牛津大学出版社.

Kruszewski, G。, & 米科洛夫, 时间. (2020). Combinatory chemistry: Towards a simple model of emergent

evolution. In ALIFE 2020: 诉讼程序 2020 conference on Artiﬁcial Life (PP. 411–419). 与新闻界.
https://doi.org/10.1162/isal_a_00258

Lafont, 是. (1997). Interaction combinators. Information and Computation, 137(1), 69–101. https://doi.org/10

.1006/inco.1997.2643

兰顿, C. G. (埃德。) (1989). Artiﬁcial Life: The proceedings of an interdisciplinary workshop on the synthesis and

simulation of living systems, 九月 1987, in Los Alamos, New Mexico. Addison-Wesley.

Lehmer, D. H. (1985). Interesting series involving the central binomial coefﬁcient. The American Mathematical

Monthly, 92(7), 449–457.

Lotka, A. J. (1910). Contribution to the theory of periodic reactions. Journal of Physical Chemistry, 14(3),

271–274. https://doi.org/10.1021/j150111a004

Maturana, H. R。, & 瓦雷拉, F. J. (1973). De máquinas y seres vivos: Una teoría sobre la organización biológica
[Of machines and living beings: A theory on biological organization]. Editorial Universitaria.

迈耶, T。, Yamamoto, L。, 班扎夫, W., & Tschudin, C. (2009). Elongation control in an algorithmic

化学, In G. Kampis, 我. Karsai, & 乙. 萨斯玛丽 (编辑。), ECAL’09: Proceedings of the 10th European
conference on advances in Artiﬁcial Life: Darwin meets von Neumann (PP. 273–280). Springer-Verlag. https://土井
.org/10.1007/978-3-642-21283-3_34

匹安多糖, S. 时间. (2021). The computational origin of representation. Minds and Machines: Journal for Artiﬁcial
智力, Philosophy and Cognitive Science, 31(1), 1–58. https://doi.org/10.1007/s11023-020-09540-9,
考研: 34305318

Pierce, 乙. C. (2002). Types and programming languages. 与新闻界.

Sayama, H. (2018). Seeking open-ended evolution in swarm chemistry II: Analyzing long-term dynamics via

automated object harvesting. In Proceedings of the ALIFE 2018: 这 2018 conference on Artiﬁcial Life
(PP. 59–66). 与新闻界. https://doi.org/10.1162/isal_a_00018, 考研: 30528047

Schönﬁnkel, 中号. (1924). Über die Bausteine der mathematischen Logik [About the building blocks of
mathematical logic]. Mathematische Annalen, 92(3), 305–316. https://doi.org/10.1007/BF01448013

Tominaga, K., Watanabe, T。, Kobayashi, K., Nakamura, M。, Kishi, K., & Kazuno, 中号. (2007). Modeling

molecular computing systems by an artiﬁcial chemistry: Its expressive power and application. Artiﬁcial Life,
13(3), 223–247. https://doi.org/10.1162/artl.2007.13.3.223, 考研: 17567243

Waldmann, J. (2000). The combinator S. Information and Computation, 159(1-2), 2–21. https://doi.org/10.1006

/inco.2000.2874

沃克, C。, & Ashby, 瓦. 右. (1966). On temporal characteristics of behavior in certain complex systems.

Kybernetik, 3(2), 100–108. https://doi.org/10.1007/BF00299903, 考研: 6003990

Wuensche, A, Lesser, M。, & Lesser, 中号. J. (1992). Global dynamics of cellular automata: An atlas of basin of attraction

ﬁelds of one-dimensional cellular automata, (卷. 1). Addison-Wesley.

Young, 时间. J。, & Neshatian, K. (2013). A constructive artiﬁcial chemistry to explore open-ended evolution. 在

S. Craneﬁeld & A. Nayak (编辑。). Australasian joint conference on artiﬁcial intelligence AI 2013: Advances in artiﬁcial
智力 (PP. 228–233). 施普林格. https://doi.org/10.1007/978-3-319-03680-9_25

294

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

Appendices

附录 1: Random Kinetics Derivations

A1.1 Equilibrium Distribution
Here we show that Equation 12 corresponds to the equilibrium distribution of the process deﬁned
by Equation 10. Plugging Equation 12 into Equation 10 we obtain:

dx∗x
dt =

cX
c0

c5
c0



X(xy)
z
=
( y x)
z
=











X( yz)
X
=

cX
c5

z
乙
e−
|
|

X( yz)
X
=

cX
c5

X
乙
e−
|

|





c2
X
c2
5

乙(

e−

)
z
y
|
|+|
|

c2
X
c2
5

X(xy)
z
=
( yx)
z
=

乙(

e−

X
|

)
y
|
|+|





(16)

(xy), 然后

(xlxr) can only be cleaved
Noting that if z
into xl and xr, while vice versa, only the condensation of xl and xr can form x, and that there are
knCn
1 possible expression of length n (where Cn stands for the nth Catalan number and k
3 是
-
the number of combinators), and that we must sum twice the factors corresponding to expression
z that can be formed either as (xy) or as (yx), then we have:

, that an expression x

| = |

| + |

c2
X
c5

knCn
-

乙(

1e−

X
|

! -

c2
X
c5

X
乙
e−
|

dxx
dt =

∞

1
c0
Xn
1
=
c2
X
c5

1
c0

e−

乙(

X
|

)
|

∞

Xn
1
=

c2
X
c5

knCn
-

乙(

1e−

X
|

(17)

This expression evaluates to 0 as long as the series converges, which we can assess using the ratio
测试, and the identity Cn

1 =
+

2(2n
1)
2 中文:
+
n
+

lim
n
→∞

kn
1Cn exp (
+
knCn
-

-
1 经验值 (

乙(
X
|
| +
乙(
X
|

| +

1))
+
n)) =

2k(2n
n

-
1

e−

乙 < 1. (18) Thus, if b > 日志(4k), then Equation 12 deﬁnes the equilibrium distribution.

A1.2 Boundary Conditions
这里, we derive the value of b by solving Equation 14. We start by showing that the following
identity holds:

knCn
-

1e−

bnn

∞

Xn
1
=

乙
ke−

√1

乙
4ke−

Artiﬁcial Life Volume 27, Number 3–4

(19)

295

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

Rearranging the terms of the series, 我们有:

∞

中文

1e−

(乙

log k)恩
-

knCn
-

1e−

bnn

∞

Xn
1
=

Xn
1
=
∞

Xn
1
=

∞

中文

1a nn
-

Xn
1
=
Cma m(米

∞

Xm
0
=

中文

1a n
1n
-
-

1),

(20)

where a
ating function for central binomial coefﬁcients (Lehmer, 1985), 第二, we obtain:

1. 然后, using the deﬁnition of Cn =

n
1
+

e−

(乙

log k), 米
-

2n
n

, 首先, and the gener-

(西德:0)

(西德:1)

Cma m(米

∞

Xm
0
=

∞

0 (西德:18)

Xn
=

(西德:19)

2米
米

a m

√1

和

< 1/4. Finally, replacing Equation 21 into 20 and expanding a, we have: knCn − 1e− bnn = ∞ Xn 1 = (b log k) e− − 1 (b 4e− − log k) = b ke− √1 − b 4ke− , 1 − p with b > log 4k. 下一个, we replace Equation 22 进入 14,

cX
c5

乙
ke−

√1

4ke−

b =

中号

and solve for b to obtain:

乙

日志





cX
c5 (西德:19)

(西德:18)

1
.
4M2 



A1.3 Normalizing Constant
下一个, we compute the normalizing constant
following identity:

knCn
-

1e−

∞

Xn
1
=

1
2

(西德:16)

乙
4ke−

(西德:17)

√1
2A

∞

Cnan

Xn
0
=

296

x x∗x. We start by showing the derivation for the

磷

Using this time the generating function for Catalan numbers (戴维斯, 2006),

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

(21)

(22)

(23)

(24)

(25)

(26)

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

we follow an analogous argument to the one above:

knCn
-

1e−

∞

Xn
1
=

∞

Xn
1
=
∞

Xm
0
=

中文

1e−

(乙

log k)n

中文

1一个
-

中文

1一个
1
-
-

∞

Xn
1
=

∞

Xn
1
=
4A

Cmam

√1
2

√1

-
2

乙
4ke−

(27)

where a

e−

(乙

log k), 米
-

1. 因此, using again that there are knCn
-

1 expressions of length n:

x∗x =

X
X

cX
c5

∞

Xn
1
=

knCn
-

1e−

cX
2c5

(西德:16)

乙
4ke−

(西德:17)

(28)

附录 2: Metabolic Cycles

The following derivations show one of the possible pathways that each of the described structures
can undertake as they develop. Whenever more than one reduction is possible, the “least effort”
path is followed, 即, I and K combinators are reduced ﬁrst, and then S combinators with the
shortest reactant (IE。, third argument). 还, note that every expression written as (( fx)(g y)) 能
also be written simply as ( fx(g y)), a fact that we often make use of when applying an S reduction.

A2.1 Metabolic Cycle of a Simple Autopoietic Pattern
Let A

(SII). 然后,

(AA)

A
+
(IA(IA))
(A(IA))

⇒
⇒
⇒

((IA)(IA))
(A(IA))
(AA)

S
我
我

+
+
+

A2.2 Metabolic Cycle of a Right-Branching Recursively Growing Structure
Let A

(S(和)我). 然后,

(AA)
A
(SIA(IA))
A
(IA(AA))

(SIAA)

⇒
⇒
⇒
⇒

(SIA(IA))
SIAA
(IA(AA))
(A(AA))

S
我
S
我

+
+
+
+

A2.3 Metabolic Cycle of a Binary-Branching Structure
Let A

(S(SSI)K). 然后 (AA) can follow the metabolic pathway:

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

(AA)
A
SSIA(KA)
A
(在(IA)(KA))
(KA)

+
+

(SAA(KA))

⇒
⇒
⇒
⇒

(SSIA(KA))
(在(IA)(KA))
(SAA(KA))
(A(KA)(A(KA)))

S
S
我
S

+
+
+
+

Artiﬁcial Life Volume 27, Number 3–4

297

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

Then each copy of (A(KA)) can be reduced as follows

(A(KA))

(SSI(KA)(K(KA))

(KA)

(S(KA)(我(KA))(K(KA)))

(S(KA)(KA)(K(KA)))

(K(KA))

(KA(K(KA))(KA(K(KA))))

(A(KA(K(KA))))

⇒

SSI(KA)(K(KA))

(S(KA)(我(KA))(K(KA)))

(S(KA)(KA)(K(KA)))

(KA(K(KA))(KA(K(KA))))

(A(KA(K(KA))))

(AA)

(K(KA))

我

the complete pathway can be summarized as (AA)

因此,
AA(AA)

4(K(KA))

2φ(A).

5(KA)

(K(KA))

⇒∗

A2.4 Metabolic Cycle of a Self-Reproducing Expression
Let A

(和(S(SK)我)). 然后,

(AA)
A
(IA(S(SK)IA))
A

(A(S(SK)IA))

(A(SKA(IA)))
(A(SKAA))
(A(KA(AA)))

⇒
⇒
⇒

(IA(S(SK)IA))
(A(S(SK)IA))
(A(SKA(IA)))

(A(SKAA))
(A(KA(AA)))
(AA)
(AA)

S
我
S

我
S
K

+
+
+

A2.5 Arrival of the Self-Reproducing Expression
In our simulations, 我们发现 (AA) with A
(和(S(SK)我)) often emerged from the conden-
=
sation of two expressions leading to a chain of reactions that resulted in (AA). Here we show one
simple path involving the condensation of (和(和)) 和 (S(SK)我) 生产 (和(和)(S(SK)我)). Let
(SIB). The reduction chain that leads to (AA) proceeds as
us call B
如下:

(S(SK)我), and note that A

(和(和)乙)

乙

+
(IBA)
A

(S(SK)IA)

(SKAA)

(SKA(IA))
A
(KA(AA))

⇒

⇒
⇒

⇒
⇒
⇒

(IBA)

(BA)
(SKA(IA))

(SKAA)
(KA(AA))
A

我
S

我
S
K

+
+

+
+
+

298

Artiﬁcial Life Volume 27, Number 3–4

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

G. Kruszewski and T. 米科洛夫

Self-Reproducing Metabolisms as Recursive Algorithms

A2.6 Metabolic Cycle of a Simple Autopoietic Pattern on the S
Let A

(S(SK)(SKK)). 然后,

K Basis

(AA)
(SKA(SKKA))

A
A
(SKA(KA(KA)))

+
+

(SKAA)

A
(KA(AA))

⇒
⇒
⇒

⇒
⇒

((SKA)(SKKA))
(SKA(KA(KA)))
KA

(SKAA)

+
(KA(AA))
(AA)
A

S
S
K

A
K

+
+
+

+
+

A2.7 Metabolic Cycle of a Recursively-Growing Expression on the S
Let A

(S(SSK)). 然后,

K Basis

(AAA)
(SSKA(AA))

(在(KA)(AA))

A
+
A
+
AA

(A(AA)(KA(AA)))

(A(AA)A)

⇒
⇒
⇒

⇒

(SSKA(AA))
(在(KA)(AA))
(A(AA)(KA(AA)))

(A(AA)A)

(AA)

+
(SSKA(AAA))

S
S
S

+
+
+

A2.8 Metabolic Cycle of a Self-Reproducing Expression on the S
Let A

(S(SK)(S(SK)(SKK))). 然后,

K Basis

(AA)
(SKA(S(SK)(SKK)A))

A
A

+
+

(SKA(SKA(SKKA)))

A
(SKA(SKA(KA(KA))))

(SKA(SKAA))

A
(SKA(KA(AA)))

(SKAA)

A
(KA(AA))

⇒
⇒

(SKA(S(SK)(SKK)A))
(SKA(SKA(SKKA)))

(SKA(SKA(KA(KA))))
(SKA(SKAA))
K

(SKA(KA(AA)))
AA

(SKAA)

+
(KA(AA))
AA

S
S

S
KA

S
K

+
+

Artiﬁcial Life Volume 27, Number 3–4

299

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你
A
r
t
我
/

我

A
r
t
我
C
e
–
p
d

F
/

2
7
3
–
4
2
7
7
2
0
0
3
2
6
9
A
r
t
我

_
A
_
0
0
3
5
5
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
下载pdf