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.