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

Basic bibliography

 


The Experimental Algorithmic Information Theory Project
by Hector Zenil

Back to the main page
Hector Zenil <hectorz[at]alumni.cmu.edu>
<hector.zenil-chavez[at]malix.univ-paris1.fr>
Laboratoire d'Informatique Fondamentale de Lille and IHPST (Paris 1)
WWW URL: "http://zenil.mathrix.org"


Links

The shortest universal machine implementation contest

"Randomness:
5 Questions" book

Useful Links

Rodney G. Downey online book on
Algorithmic Randomness and Complexity

Andrei Kolmogorov
web page

The 2,3 Wolfram Turing Machine Research Prize

Gregory Chaitin
homepage

Leonid Levin's
web page

Ray Solomonoff
web page

Cristian Calude
web page

Busy beaver from MathWorld

NKS online book

Turing machines from the Stanford Encyclopedia of Philosophy

Rod Downey
home page

Ming Li
home page

Paul Vitanyi
home page

Jan Reimann
home page

Douglas Cenzer
home page

André Nies
web page

Eric Allender
web page

Jean-Paul Delahaye
web page

Heiner Marxen
busy beaver page

Maurice Margenstern
home page

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