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

John R. Woodward, Amin Farjudian

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

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 0s and 1s. 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 scenario, 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.

Original languageEnglish
Title of host publicationProceedings of the 2010 IEEE International Conference on Progress in Informatics and Computing, PIC 2010
PublisherIEEE Computer Society
Pages1266-1269
Number of pages4
ISBN (Print)9781424467860
DOIs
Publication statusPublished - 2010

Publication series

NameProceedings of the 2010 IEEE International Conference on Progress in Informatics and Computing, PIC 2010
Volume2

Keywords

  • Complexity
  • Compression
  • Entropy
  • Gzip
  • Huffman code
  • Life
  • Randomness
  • Thermodynamics
  • Tierra

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Information Systems

Fingerprint

Dive into the research topics of 'Artificial life, the second law of thermodynamics, and Kolmogorov complexity'. Together they form a unique fingerprint.

Cite this