  One of the main goals of Artificial Life is to research the conditions for
the emergence of life, not necessarily as it is, but as it could be. Artificial
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, and ultimately, 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. In this paper,
we hypothesize that the key property needed for self-reproducing metabolisms to
emerge is the existence of an auto-catalyzed subset of Turing-complete
reactions. We validate this hypothesis with a minimalistic Artificial Chemistry
with conservation laws, which is based on a Turing-complete rewriting system
called Combinatory Logic. Our experiments show that a single run of this
chemistry, 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.
