Experimental Algorithmic Information Theory (EAIT)

What is Experimental Algorithmic Information Theory?

We have coined the term Experimental Algorithmic Information Theory (EAIT) to emphasize the experimental character of our research. A founder of EAIT would beGregory Chaitin who together with Nicolai Kolmogorov, Ray Solomonoff and Leonid Levin have created most of the AIT field (sometimes also called program-size or Kolmogorov complexity). Greg Chaitin has particularly pushed the idea of a quasi-empirical approach to mathematics by performing experiments and running programs, dicting a paradigm shift concerning the way in which math is done. An approach also pioneered by Stephen Wolfram and his NKS. We are taking this dictums for a hands-on approach to algorithmic information theory (AIT).

Our research program focus on:

• The problem and evaluation of the algorithmic complexity for short strings: a well-known problem due to the short length of strings to be approached by compressibility methods.
• On finding a framework for stable enough for the definition of program-size complexity independent (or reduced) of additive constants.
• An information content approach to the notion of "naturalness" in a model of computation.
• The relation between program-size and computational time complexity.
• Comparing output probability distributions for as many models of computation as possible, such as abstract machines and physical sources of information to find and plot a taxonomic tree of correlations, if any.
• Finding actual applications, from providing distribution tables for compression purposes to Bayesian prior probabilities.

Selected papers on EAIT

- Jean-Paul Delahaye and Hector Zenil, 'Towards a stable definition of Kolmogorov-Chaitin complexity', submitted to Fundamenta Informaticae, 2008. (arXiv:0804.3459v1 [cs.IT])

- 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, Singapore, 2007. (arXiv:0704.1043v3 [cs.CC]). Article webpage with source code and the detailed results.

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.