|
|
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

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.

The Experimental Algorithmic Information Theory Project
by Jean Paul Delahaye and Hector Zenil
Back to the main page
Hector Zenil <hectorz [at-] andrew.cmu.edu>
<hector.zenil [at-] lifl.fr>
Laboratoire d'Informatique Fondamentale de Lille and IHPST (Paris 1)
WWW URL: "http://zenil.mathrix.org"
|
 |
Links
The shortest universal machine implementation contest
Gregory Chaitin
Leonid Levin's
Ray Solomonoff
Cristian Calude
Rodney G. Downey online book on
Algorithmic Randomness and Complexity
Andrei Kolmgorov
web page The 2,3 Wolfram Turing Machine Research Prize
Busy beaver from MathWorld NKS online book
Turing machines from the Stanford Encyclopedia of Philosophy
Rod Downey
Ming Li
Paul Vitanyi
Jan Reimann Douglas Cenzer
André Nies
Eric Allender
Jean-Paul Delahaye
Heiner Marxen
busy beaver page
Maurice Margenstern
Algorithmic randomness from Scholarpedia
Algorithmic complexity
from Scholarpedia
Applications of AIT
from Scholarpedia Algorithmic probability
from Scholarpedia
Pascal Michel's Historical survey of busy beaver results Michael Somos
web page
Allen H. Brady
web page
Algorithmic Information Theory by Marcus Hutter Laboratoire d'Informatique Fondamentale de Lille
Institute d'Histoire et Philosophie des Sciences et Techniques
|