Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Approximations to Algorithmic Probability

  • Hector ZenilEmail author
Living reference work entry
DOI: https://doi.org/10.1007/978-3-642-27737-5_700-1

A Computational Theory of Everything

Physicists have long been searching for a so-called Theory of Everything (ToE). Just as quantum mechanics explains the smallest phenomena, from microwaves to light, and general relativity explains the classical world, from gravity to space and time, a ToE would explain everything in the universe, from the smallest to the largest phenomena, in a single formulation.

Science has operated under the assumption and in light of strong evidence that the world is highly, if not completely, algorithmic in nature. If the world were not structured, our attempts to construct a body of theories from observations, to build what we consider ordered scientific models of the world, would have failed. That they have not is spectacular vindication of the validity of the world’s orderly character. We started out believing that the world was ruled by magic, and by irrational and emotional gods. However, thinkers from ancient civilizations such as China and India and,...

This is a preview of subscription content, log in to check access.


  1. Delahaye J-P, Zenil H (2012) Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness. Appl Math Comput 219(1):63–77zbMATHGoogle Scholar
  2. Gauvrit N, Singmann H, Soler-Toscano F, Zenil H (2016) Algorithmic complexity for psychology: a user-friendly implementation of the coding theorem method. Behav Res Methods 48(1):314–329CrossRefGoogle Scholar
  3. Gauvrit N, Soler-Toscano F, Zenil H (2014) Natural scene statistics mediate the perception of image complexity. Vis Cogn 22(8):1084–1091CrossRefGoogle Scholar
  4. Gauvrit N, Zenil H, Delahaye J-P, Soler-Toscano F (2014) Algorithmic complexity for short binary strings applied to psychology: a primer. Behav Res Methods 46(3):732–744CrossRefGoogle Scholar
  5. Gauvrit N, Zenil H, Soler-Toscano F, Delahaye J-P, Brugger P (2017) Human behavioral complexity peaks at age 25. PLoS Comput Biol 13(4):e1005408CrossRefGoogle Scholar
  6. Gauvrit N, Zenil H, Tegnér J (2017) The information-theoretic and algorithmic approach to human, animal and artificial cognition. In: Dodig-Crnkovic G, Giovagnoli R (eds) Representation and reality: humans, animals and machines. Springer, New YorkGoogle Scholar
  7. Gregory J, Chaitin GJ (1966) On the length of programs for computing finite binary sequences. J ACM 13(4):547–569MathSciNetCrossRefzbMATHGoogle Scholar
  8. Kirchherr W, Li M, Vitányi P (1997) The miraculous universal distribution. Math Intell 19:7–15MathSciNetCrossRefzbMATHGoogle Scholar
  9. Levin LA (1974) Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Probl Peredachi Inf 10(3):30–35Google Scholar
  10. Schmidhuber J (2002) Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. Int J Found Comput Sci 13(4):587–612MathSciNetCrossRefzbMATHGoogle Scholar
  11. Shannon CE (1948) A mathematical theory of communication parts i and ii. Bell Syst Tech J 27:379–423. and 623–656CrossRefzbMATHGoogle Scholar
  12. Soler-Toscano F, Zenil H, Delahaye J-P, Gauvrit N (2014) Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. PLoS One 9(5):e96223ADSCrossRefGoogle Scholar
  13. Solomonoff RJ (1964) A formal theory of inductive inference. Part i. Inf Control 7(1):1–22MathSciNetCrossRefzbMATHGoogle Scholar
  14. Tegnér J, Zenil H, Kiani NA, Ball G, Gomez-Cabrero D (2016) A perspective on bridging scales and design of models using low-dimensional manifolds and data-driven model inference. Phil Trans R Soc A 374(2080):20160144ADSCrossRefGoogle Scholar
  15. Wolfram S (2002) A new kind of science. Wolfram Media, ChampaignzbMATHGoogle Scholar
  16. Zenil H (2011) The world is either algorithmic or mostly random, 2011. Winning 3rd place in the international essay context of the FQXiGoogle Scholar
  17. Zenil H (2013) A behavioural foundation for natural computing and a programmability test. In: Dodig-Crnkovic G, Giovagnoli R (eds) Computing nature. Springer, New York, pp 87–113CrossRefGoogle Scholar
  18. Zenil H (2014a) Programmability: a Turing test approach to computation. In: L. De Mol, G. Primiero, (eds) Turing in context, Koninklijke Vlaamse Academie van België voor Wetenschappen en Kunsten (Belgian Academy of Sciences and Arts), Contactforum. Belgian Academy of Sciences and ArtsGoogle Scholar
  19. Zenil H (2014b) What is nature-like computation? A behavioural approach and a notion of programmability. Philos Technol 27(3):399–421CrossRefGoogle Scholar
  20. Zenil H (2015) Algorithmicity and programmability in natural computing with the game of life as in silico case study. J Exp Theor Artif Intell 27(1):109–121CrossRefGoogle Scholar
  21. Zenil H, Delahaye J-P (2010) On the algorithmic nature of the world. In: Dodig-Crnkovic G, Burgin M (eds) Information and computation. World Scientific, LondonGoogle Scholar
  22. Zenil H, Kiani NA, Tegnér J (2016) Methods of information theory and algorithmic complexity for network biology. Semin Cell Dev Biol 51:32–43CrossRefGoogle Scholar
  23. Zenil H, Kiani N, Jesper T (2017) Low algorithmic complexity entropy-deceiving graphs. Phys Rev E 96(012308)Google Scholar
  24. Zenil H, Soler-Toscano F, Dingle K, Louis AA (2014) Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks. Physica A Stat Mech Appl 404:341–358MathSciNetCrossRefGoogle Scholar
  25. Zenil H, Soler-Toscano F, Kiani NA, Hernández-Orozco S, Rueda-Toicen A (2016) A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity. arXiv preprint arXiv:1609.00110Google Scholar
  26. Zenil H. (2017) Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation. In M. Ott, W. Pietsch, J. Wernecke (eds.), Berechenbarkeit der Welt? Philosophie und Wissenschaft im Zeitalter von Big Data (Computability of the World? Philosophy and Science in the Age of Big Data), Springer Verlag, pp. 453-475Google Scholar

Copyright information

© Springer Science+Business Media LLC 2017

Authors and Affiliations

  1. 1.Algorithmic Dynamics Lab, Unit of Computational Medicine and SciLifeLab, Center for Molecular Medicine, Department of Medicine SolnaKarolinska InstitutetStockholmSweden