4.4 Algorithmic Complexity and Compressibility
Channel: Complexity Explorer
Date: 2018-08-20

Unit 4 Module 4
Algorithmic Information Dynamics: A Computational Approach to Causality and Living Systems---From Networks to Cells
by Hector Zenil and Narsis A. Kiani

Algorithmic Dynamics Lab
www.algorithmicdynamics.net

Demonstration source code: http://demonstrations.wolfram.com/CellularAutomatonCompressibility/

Refs:

http://demonstrations.wolfram.com/CellularAutomatonCompressibility/

- G.J. Chaitin. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987.

- A.N. Kolmogorov, "Three approaches to the quantitative definition of information," Problems of Information Transmission 1, 1-11, 1965.

- F. Soler-Toscano, H. Zenil, J.-P. Delahaye, N. Gauvrit, Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines, arXiv:1211.1302 [cs.IT]

- R. J. Solomonoff, "A formal theory of inductive inference: Parts 1 and 2. Information and Control," 7:1--22 and 224--254, 1964.

- A. K. Zvonkin and L. A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms," Russian Mathematical Surveys, 25(6):83--124, 1970.

- L.A. Levin, "Laws of information conservation (non-growth) and aspects of the foundation of probability theory," Problems Information Transmission, 10(3):206-210, 1974.

- R. J. Solomonoff, "Algorithmic Probability\[LongDash]Its Discovery\[LongDash]Its Properties and Application to Strong AI," In H. Zenil (ed), Randomness Through Computation: Some Answers, More Questions, World Scientific, 2012.

- H. Zenil, Compression-based Investigation of the Dynamical Properties of Cellular Automata and Other Systems, Complex Systems, vol. 19, No. 1, pp. 1-28, 2010.

- H. Zenil, Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces, International Journal of Bifurcation and Chaos vol. 23, no. 9, 2013.