v1i2 80 Letters and Notes the data, the more they classify each sample incorrectly. Russell, S and P Norvig (2009). Artificial Intelligence: A Modern Approach. 3rd ed. Pearson. The Possibility of Spontaneous Generation of Self-Replicating Systems Gary Prok DOI: 10.33014/issn.2640-5652.1.2.prok.1 It has been glibly stated that given enough time, a universe of monkeys at typewriters could write Hamlet. If this is true then perhaps the universe of particles could accidently assemble the right configuration of stuff to spark life. Yet the universe today is not even old enough to allow all the resources in the visible universe to work together with the tiniest probability of success to randomly generate the first 200 characters of Hamlet. A shorter 142-character string of the start of Hamlet is a unique string of information which is of 10210 possible strings of 142 characters. 10210 random tries would give a chance of ! 1 − 1 e " , or ~63%, for generat- ing this simple 142-character passage. This might be only for a fleeting instant at some corner of the universe, but nonetheless it would be spontaneously generated. Adding another 58 characters to total 200 characters reduces the chance to a minuscule value. Spontaneous generation of life it seems, would require even more resources or time. Seth Lloyd has estimated the computational capacity of the universe to be 10120 operations from the start to date, on a register of 1090 bits (Lloyd, 2002). A register of 1090 bits contain nearly 1090 different 142-character length strings. So, the universe could generate at most 10210 tries to date. 10210 is approximately 2700, or all of the possible permu- tations of 700 bits. Although this computational capacity cannot generate Hamlet in its entirety by chance, or even the first 200 characters, perhaps it can be shown to be suf- ficient to spontaneously generate life. Another bound was offered by Dembski as 10150, or approx- imately all the possible permutations of 500 bits (Dembski, 1998, pg. 213). This is more restrictive, but may be a more realistic estimate for practical things like the probability of spontaneous life. One way of quantifying the needed time and resources is to consider a simple proxy for life. A proxy for abiogenesis requires a simple system that allows a means for an informa- tion string to induce its own replication as well as a means to execute this replication. This proxy could be a simple system of things that operate on such things to make more such things. Lambda calculus is a system of mathematical logic reduced to a minimal set of symbols and rules. Ex- pressions in lambda calculus can operate on other such ex- pressions to generate more such expressions. Furthermore, lambda calculus is a universal model of computation and is Turing complete. It is enlightening to see how much infor- mation is needed to describe a simple self-replicating set of statements in lambda calculus. If a universe of monkeys or of particles can generate this simple set of statements, then perhaps it can do the same with material stuff and spark life. Lambda calculus is considered to be a minimally simple programming language; it is hard to conceive of a simpler language. It was created by Alonzo Church as part of his research into the foundation of mathematics and uses three simple rules, yet it is capable of expressing any computa- tion. Its simplicity results in bloated expressions for simple concepts, like numbers, or “true” and “false”. Its simplicity, however, also makes it a model for a system most likely to spontaneously generate. The fundamental concept allowed by lambda calculus is substitution. (λx.fx) is an expression in lambda calculus where ”λ” indicates that the next variable is a free variable to be substituted, “x” is the name of the free variable, and “.” indicates that what follows is an expression or function in which the free variable is to be substituted. The value or expression to be substituted for x is placed to the right of the expression. As an example, (λx.x2) y = y2, where y is substituted for x. This substitution is called abstrac- tion. Lambda calculus also allows for application, which is a function operating on an argument. A tutorial of lambda calculus is not included here, but is readily found elsewhere. Lambda calculus can be efficiently encoded in binary; bi- nary lambda calculus (BLC) is an efficient way to encode expressions in lambda calculus into binary (Tromp, 2007). BLC uses De Bruijn indices instead of variables, where the index value is a natural number indicating how many λs back the variable refers. λx.λy.xy is written as λ λ 2 1 with De Bruijn indices (Bruijn, 1972). Three things that Volume 1, Issue 2 The Possibility of Spontaneous Generation of Self-Replicating Systems 81 then need to be encoded into binary are abstraction (λ), application, and natural numbers. The scheme is very sim- ple: Abstraction (λ) is encoded as 00 Application is encoded as 01 Natural number n is encoded as 111110. . . (where there are n 1s) λx.λy.xy is written as λ λ 2 1 with De Bruijn indices, which in BLC is 00 00 01 110 10 (spaces added for understanding). Lambda expressions are executed by the process of beta- reduction. This means of execution can also be expressed in lambda calculus and encoded in BLC. Lambda calculus can express a list using the PAIR function. Other lambda expressions can extract any particular element of a list. The following elements comprise a self-replicating system in lambda calculus: • The self-replicating combinator Q; QQ -> QQ does not propagate on beta-reduction, it merely replaces itself. However, QE ((QE) nil) does propagate QE on beta- reduction, by creating a growing list of (QE), (QE), (QE). . . . (QE), nil (E is defined below). QE will prop- agate any expression, P; QE (P nil) will generate a growing list of P, P, P,. . . . P . • A beta-reduction engine is required. – If this engine were encoded into P, then a means to translate from the information space to ma- chine space also would be required and the initial instance would have no machine with which to execute. – The least required total Kolmogorov complexity would have the beta reduction engine simulta- neously generated in the machine state, as op- posed to being generated in the information media state and subsequently transcripted to the ma- chine state. The engine would act like a single instance of a re-usable catalyst, operating on the growing list. A minimal self-replication system in lambda calculus would generate a growing list of copied expressions, like (QE), (QE), (QE). . . . (QE), nil. This would require: • A means to encode Lambda calculus. BLC is an effi- cient means. • The E combinator, encoded in an information media state, like DNA/RNA in life. • The self-replicating combinator Q, encoded in the in- formation media state. • A program for self-reduction – encoded in the machine state, like an enzyme protein assemblage in life. The total information requirement to generate the minimal proxy for abiogenesis is then: • E, which operates on a list and extends it by one ele- ment (based on Larkin and Stocks, 2004). E = λx. (λp.(λl.xxp(PAIR pl))) , which in BLC is 000000111111111011101100000001011101011010 (42 bits long). • Q, the self-application combinator. Q = λx. xx which in BLC is 00011010 (8 bits long). • The application of Q to E, QE, which adds 2 bits. • Nil, which is λz.λx.λy.x, adding 9 bits. • Two more applications to create the expression QE ((QE) nil), adding 4 more bits • A beta-reduction engine in machine space to process ((QE) E nil). This would at a minimum require: a. A true statement: λx.λy.x (7 bits) b. A false statement: λx.λy.y (6 bits) c. An if-then-else statement: λz.λx.λy.zxy (15 bits) d. Abstractions to delete and replace expressions (>~15bits each, or >~30bits). The bit count so far for a beta reduction engine is > 58. Actual construction of the beta reducer could require many more. A beta-reduction engine in an abstracted lambda calculus has been found, which is longer than 200 bits (Mogensen, 1994). An engine in BLC would require a similar number of bits. So far we are up to many more than 123 bits, and likely more than 265 bits, for a randomly-formed pair of infor- mation strings, one in information space (DNA/RNA) and one in machine space (protein/enzyme) which allows the information string to propagate in a list. It may be possible to compress these relatively short strings. E in particular appears to be a compressible string, which 82 Letters and Notes might allow for a reduced bit count. However, adding a codec to the mix will certainly increase the bit count more than it offers in compressive bit-reduction. It is reasonable to think that a minimal basic precursor to abiogenisis of life would require two random assemblages with total information exceeding 265 bits. However, 265 bits is below the 500 bit Dembski limit and below the 700 bit limit based on Seth Lloyd’s analysis. This analysis does not rule out the spontaneous, if fleeting, generation of a self-replicating system somewhere in the universe at some time in its past. The probability given the Dembski limit is! 1 − 1 e (500/265) " , or ~85%. The probability given the 700 bit limit is ! 1 − 1 e (700/265) " , or ~93%. Appending other features on to this analysis will require more bits. Examples are: • A means for the information describing the beta- reduction engine in the machine space to be also ex- pressed in the information space. • A means for the information expressed in the informa- tion space to be realized in the machine space, they way a genotype becomes a phenotype in life. • A means to operate on more than the first element in the list to allow population growth that approaches exponential. This will require information to describe recursion on the TAIL function. • A means to store the information and the beta- reduction engine in the physical world. Although these are needed and may well push the informa- tion needs above 700 bits, they are beyond the scope of this analysis. This analysis does not rule out a single instance of the spon- taneous generation of a self-replicating system somewhere in the universe. It does, however, suggest that this is an ex- traordinarily rare event. This analysis suggests that there is less than 50% likelihood that 10 self-replicating systems have spontaneously generated in the universe. Given the vastness of the spacetime of the universe, an implication is that any evidence of extra-terrestrial life would be evidence of transpermia. Bruijn, N G de (1972). “Lambda calculus notation with nameless dummies, a tool for automatic formula ma- nipulation, with application to the Church-Rosser the- orem”. In: Indagationes Mathematicae 75 (5), pp. 381– 392. url: http://alexandria.tue.nl/repository/ freearticles/597619.pdf. Dembski, W A (1998). The Design Inference: Eliminating Chance Through Small Probabilities. Cambridge: Cam- bridge University Press. Larkin, J and P Stocks (2004). “Self-Replicating Expres- sions in the Lambda Calculus”. In: Proceedings of the Twenty-Seventh Australasian Computer Science Con- ference (ACSC2004). Ed. by V Estivill-Castro. Dunein, New Zealand, pp. 167–173. Lloyd, S (2002). “The Computational Universe”. In: Edge.org. url: https : / / www . edge . org / conversation/seth%5C_lloyd-the-computational- universe. Mogensen, T (1994). “Efficient Self-Interpretation in Lambda Calculus”. In: Journal of Functional Program- ming 2.3. Tromp, J (2007). “Binary Lambda Calculus and Combi- natory Logic”. In: Randomness And Complexity, from Leibniz To Chaitin. Ed. by C S Calude. World Scientific Publishing Company, pp. 237–260.