Artificial life, the second law of thermodynamics, and Kolmogorov complexity

Citation

Woodward J & Farjudian A (2010) Artificial life, the second law of thermodynamics, and Kolmogorov complexity. In: 2010 IEEE International Conference on Progress in Informatics and Computing (PIC), Volume 2. 2010 IEEE International Conference on Progress in Informatics and Computing (PIC), Shanghai, 10.12.2010-12.12.2010. Piscataway, NJ: IEEE, pp. 1266-1269. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5687924&abstractAccess=no&userType=inst; https://doi.org/10.1109/PIC.2010.5687924

Abstract
One of the basic features of life is replication. Indeed one of the three components of evolution is inheritance, which implies some similarity (both phenotypic and genotypic) between parents and offspring. Life is a process and not a substance (e.g. being carbon-based does not capture what life is), and this therefore justifies an algorithmic definition. Artificial life is concerned with the study of synthetic life, and is implemented on a digital computer. Tierra is a particularly prominent instance, where rudimentary life forms compete for space and time. In this system interesting eco-systems emerge, for example demonstrating parasitic behavior. The second law of thermodynamics states that the entropy of an isolated system is nondecreasing. The second law is a consequence of statistics, and that there are many more states with high entropy than low entropy. Entropy has connections with coding theory, data compression and Kolmogorov Complexity, as well as thermodynamics and statistical mechanics. When transmitting a coded message, the length of the message is proportional to the entropy. The shortest computer description is a universal code which is good for all probability distributions. The second law could therefore be restated as the Kolmogorov Complexity of a system is nondecreasing. Kolmogorov Complexity is incomputable, however we can use compression tools to give an approximate upper bound. We implement a simple digital world consisting of a bit string of Os and Is. We implement a system like Tierra, firstly with just thermal noise and no life and observe that the compression size of the world increases according to the second law. Secondly we introduce Tierra-like creatures which replicate, and observe that the size of the compressed world decreases. The question we address in this paper is, does the basic replication mechanism underpinning life cause a decrease in entropy. The contribution of this paper is a demonstration, that in an artificial life sce- - nario, entropy, as measured by a compression algorithm, decreases violating the second law of thermodynamics. Thus we can use this as an algorithmic definition of the process of life.