Experimental Algorithmic Information Theory (EAIT)

Since the days of Newton and Leibniz, scientists have constructed an increasingly elaborate view of the world.

In modern times quantum mechanics has revolutionized our understanding of physical reality at atomic scales, while general relativity has done the same for our understanding of reality at large scales. Quantum mechanics and the study of nonlinear dynamics, however, have shown that even the classical physics of Newton has randomness and unpredictability at its core.

Some contemporary scientists have recently come up with theories in which Nature is seen as an information processor, continuously computing the laws of physics and everyting we see around including all sort of complex things like life and the universe itself.

There are views supporting the thesis that Nature performs (only) digital computation up to a maximal level (e.g. Fredkin, Wolfram), and those who believe that Nature does not only perform but actually is a quantum computer (e.g. Lloyd, Deutsch). These authors degrees of believe go from the mere metaphor to the matter of fact. From being of epistemological value to an ontological posit.

This contemporary view of an algorithmic universe is closely related to a contemporary mathematical field of research called algorithmic information theory (AIT). Some AIT researchers think that the true nature of Nature can only be explained by the study of complexity and randomness (Chaitin, Levin).

We are interested in the question of whether Nature is a computer or not, and if so what kind of computer. We think the question is currently within the scope of modern scientific research and therefore a falsifiable statement. We think there might be evidence in either direction coming from the comparison between the outcome of the world itself and the expected output of a (digital) computer.

What is EAIT?

We have coined the term Experimental Algorithmic Information Theory or EAIT to emphasize the experimental character of our research.

Nicolai Kolmogorov together with Ray Solomonoff, Leonid Levin and Gregory Chaitin have created the AIT field, which is sometimes referred to as program-size, algorithmic or just Kolmogorov complexity. Greg Chaitin has been a particularly forceful advocate of a quasi-empirical approach to mathematics—one that involves performing experiments and running programs--to initiate a paradigm shift in the way math is done. This approach is consonant with the one proposed by Stephen Wolfram in his New Kind of Science (NKS). Working within this new paradigm, we are developing a hands-on approach to AIT.

Our research program is therefore focused on:

• The problem (not only because it is non-computable but hard to evaluate and dependent on additive constants) of the actual calculation of the program-size complexity for certain strings: particularly the short since they are already too short to be approached by compression algorithms. And providing a stable definition of program-size complexity independent of additive constants.
• The actual evaluation of the logical depth of a certain strings by exhaustive means and independent of additive constants, particularly the short. And providing a general stable definition of logical depth independent of additive constants.
• The formulation of a framework for a stable definition of program-size complexity independent of additive constants.
• An information content approach to the notion of "naturalness" and "exactness" for a model of computation (or actual machine implementation), namely a programming language or a universal Turing machine.
• The relation between program-size and computational time complexity, particularly the still unkown tradeoffs.
• The thorough study of the output ditribution of certain classes of computation, including runtimes.
• Comparing the output probability distributions for as many models of computation as possible, such as Turing machines, cellular automata, Post tag systems, rewriting systems, sk combinatorics, register machines, finite automata, etc., and physical sources of information, such as random images, sounds, DNA sequences and so on.
• The study of possible statistical correlations and probable mathematical convergence in output distribution.
• The devise of actual applications: from providing actual universal distribution tables for compression and other purposes to providing useful Bayesian prior distributions.

Selected papers about or related to EAIT

- Jean-Paul Delahaye and Hector Zenil, 'On the Kolmogorov-Chaitin complexity for short sequences', in 'Randomness and Complexity: From Leibniz to Chaitin' , edited by Cristian S Calude (University of Auckland, New Zealand), World Scientific, 2007. (long version available online: arXiv:0704.1043v3 [cs.CC]).

- Jean-Paul Delahaye and Hector Zenil, 'On the algorithmic complexity correlation between information from physical sources and the output of abstract computing machines', (per invitation by the eds.) in Mark Burgin, Gordana Dodig-Crnkovic (eds)., 'Information and Computation', World Scientific, 2010.

- Jean-Paul Delahaye, Nicolas Gauvrit and Hector Zenil, 'Towards a stable definition of Kolmogorov-Chaitin complexity', to be submitted to Theoretical Computer Science.

- Jean-Paul Delahaye and Hector Zenil, 'Exact evaluations of the algorithmic complexity and logical depth of short strings by means of exhaustive computation', to be submitted to the journal of Experimental Mathematics.

- Hector Zenil, 'Godel's and Turing's deepest view of the Universe', to be submitted to Complex Systems journal.

- Hector Zenil, 'Compression-based classification and clustering of Cellular Automata', submitted to Complex Systems journal.

Online resources

• Randomness in Arithmetic: Code from "Algorithmic Information Theory" code in Mathematica available online by Gregory Chaitin.
• Cristian S. Calude's Website (many papers available online and other references) .
• Applications of algorithmic information theory, from Scholarpedia by Ming Li and Paul M.B. Vitanyi.
• G J Chaitin Home Page (many of his papers are available here).
• "Computo ergo sum." David H. Bailey Home Page.
• RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR
• Doron Zeilberger Home Page.
• Kolmogorov, a web site dedicated to Andrei Nikolaevich Kolmogorov.
• Introduction to Algorithmic Information Theory by Marcus Hutter (many other online resources listed here).
• Algorithmic Information Theory, Scholarpedia by Marcus Hutter.
• Experimental Mathematics from MathWorld.
• Experimental Mathematics journal.
• Seth Lloyd Home Page.
• Experimental Mathematics from Wikipedia.
• Experimental Mathematics Website by Bailey and Borwein.
• A tutorial on Algorithmic Information Theory by Nick Szabo.
• The Alan Turing Home Page, a web site dedicated to mathematician Alan Turing. Maintained by Andrew Hodges.
• The Talk Origins, Algorithmic Information Theory (Chaitin, Solomonoff & Kolmogorov) by Rich Baldwin

Basic bibliography

• Chaitin, G.J., Algorithmic Information Theory. Third Printing, Cambridge University Press, 1990.
• Calude, CS. (ed), Randomness and Complexity, from Leibniz to Chaitin, World Scientific, Singapore, 2007.
• Calude, CS. Information and Randomness. An Algorithmic Perspective, 2nd Edition, Revised and Extended, Springer-Verlag, 2002.
• C. S. Calude, M. J. Dinneen. Exact approximations of omega numbers, Int. Journal of Bifurcation & Chaos, 17, 6 (2007), 1937-1954.
• Turing, A.M., On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-265; corrections, Ibid, vol 43 (1937) pp. 544-546.
• "Turing Machine", The Stanford Encyclopedia of Philosophy (Spring 2002 Edition), Edward N. Zalta (ed.).
• Hilbert, D., Mathematical Problems: Lecture Delivered before the International Congress of Mathematicians at Paris in 1900, translated by Maby Newson, Bulletin of the American Mathematical Society 8 (1902), pp. 437-479. , HTML version by D. Joyce available on-line.
• Gödel, K., On Formally Undecidable Propositions of Principia Mathematica and Related Systems. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated by Martin Hirzel.
• Copeland, B. Jack, "The Church-Turing Thesis", The Stanford Encyclopedia of Philosophy (Fall 2002 Edition), Edward N. Zalta (ed.).
• Hodges, Andrew, "Alan Turing", The Stanford Encyclopedia of Philosophy (Summer 2002 Edition), Edward N. Zalta (ed.).
• Minsky, M., "Size and Structure of Universal Turing Machines," Recursive Function Theory, Proc. Symposium. in Pure Mathematics, 5, American Mathematical Society, 1962, pp. 229-238.
• Ming Li and Paul M. B. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications (Texts in Computer Science), Springer, 1997.
• Rogozhin, Y. "Small Universal Turing Machines." Theoretical Computer Science 168 iss. 2, 215-240, 1996.
• Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 706-711, 2002.