home   search  Algorithmic Information Theory  contact   up 

Andrei Kolmogorov William of Ockham

Andrei Kolmogorov The theory of probability ... can and should be developed from axioms ...

Entities should not be multiplied unnecessarily William of Occam


Introduction / What is AIT?

Algorithmic Information Theory (AIT) is a subfield of information theory and computer science (and statistics and recursion theory) that concerns itself with the relationship between computation, information, and randomness. The key concepts or subfields are:

Algorithmic "Kolmogorov" Complexity (AC). Kolmogorov defined the complexity of a string x as the length of its shortest description p on a universal Turing machine U (K(x)=min{l(p):U(p)=x}). A string is simple if it can be described by a short program, like "the string of one million ones", and is complex if there is no such short description, like for a random string whose shortest description is specifying it bit-by-bit. Kolmogorov complexity is a key concept in (algorithmic) information theory. An important property of K is that it is nearly independent of the choice of U. Furthermore it leads to shorter codes than any other effective code. K shares many properties with Shannon's entropy (information measure) S, but K is superior to S in many respects. To be brief, K is an excellent universal complexity measure, suitable e.g. for quantifying Occam's razor. The major drawback of K as complexity measure is its incomputability. So in practical applications it has always to be approximated, e.g. by MML/MDL or Lempel-Ziv compression or others.

Algorithmic "Solomonoff" Probability (AP). Solomonoff defined the closely related universal a priori probability M(x) as the probability that the output of a universal Turing machine U starts with x when provided with fair coin flips on the input tape. M can be used as a universal sequence predictor that outperforms (in a certain sense) all other predictors.

Universal "Levin" Search (US). The major drawbacks of AC and AP are their incomputability. Time-bounded ``Levin'' complexity penalizes a slow program by adding the logarithm of its running time to its length. This leads to computable variants of AC and AP, and Universal ``Levin'' Search (US) that solves all inversion problems in optimal (apart from some multiplicative constant) time.

Algorithmic "Martin-Loef" Randomness (AR). AC and AP also allow a formal and rigorous definition of randomness of individual strings that does not depend on physical or philosophical intuitions about nondeterminism or likelihood. Roughly, a string is algorithmically ``Martin-Loef'' random if it is incompressible in the sense that it's algorithmic complexity is equal to its length.

Applications of AIT AC, AP, US, and AR are the core subdisciplines of AIT, but AIT spans into many other areas. It serves as the foundation of the Minimum Description Length (MDL) principle, can simplify proofs in computational complexity theory, has been used to define a universal similarity metric between objects, solves the Maxwell daemon problem, and many others.

AIT Mailing List

The Algorithmic Information Theory (AIT) mailing list is a moderated mailing list intended for people in Information Theory, Computer Sciences, Statistics, Recursion Theory, and other areas or disciplines with interests in AIT. Researchers in these fields are encouraged to join the list and participate. You're invited to discuss and exchange ideas regarding any AIT or related aspect. Software, conferences, courses, jobs, and related announcements are also welcome. You can post, read, and reply messages solely on the Web. You can choose to receive messages as individual emails, daily summaries, daily full-text digest, or read them on the Web only.

Introductory Online Material







Some Online Papers


Research field abbreviations:

Algorithmic Information Theory (AIT),
Kolmogorov Complexity (KC),
Algorithmic Probability (AP),
Algorithmic Randomness (AR),
Universal Levin Search (US),
Artificial Intelligence (AI),
Machine Learning (ML),
Minimum Description Length (MDL),
Minimum Message Length (MML),
Computational Complexity (CC).

Eric AllenderRutgers University, New Jersey, USA (AR)
Klaus Ambos-SpiesUniversität Heidelberg, Germany (AR)
Eugene AsarinUniversité Joseph Fourier, Grenoble, France
Luis AntunesUniversity of Porto, Portugal (AIT)
Maxim BabenkoMoscow State University, Russia (KC)
Janis BarzdinsUniversity of Latvia (AIT)
Verónica BecherUniversity of Buenos Aires, Argentina (AR,KC)
Harry BuhrmanCWI and University of Amsterdam, The Netherlands (AR,KC)
Cristian S. CaludeUniversity of Auckland, New Zealand (AR)
Gregory J. ChaitinIBM Research, Yorktown Heights, NY, USA (AR,AI)
Alexey ChernovIstituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (KC,CC)
Thomas CoverStanford University, CA, USA (AIT,other)
David DoweMonash University, Melbourne, Australia (MML)
Rodney G. DowneyVictoria University, New Zealand (AR)
Bruno DurandUniversité de Provence, Marseille, France
Allan ErskineUniversity College London, UK (ML,KC)
Santiago FigueiraUniversity of Buenos Aires, Argentina (AR,KC)
Lance FortnowUniversity of Chicago, USA (CC)
Péter GácsBoston University, USA (AIT)
Alex GammermanRoyal Holloway University, London, UK (AIT,ML)
Murray Gell-MannSanta Fe Institute, USA (AIT,other)
Peter GrünwaldCWI and Eindhoven University of Technology, The Netherlands (MDL)
Denis R. HirschfeldtUniversity of Chicago, USA (AR)
John HitchcockUniversity of Wyoming, Laramie, WY, USA (AIT,CC)
Achim HoffmannUniversity of New South Wales, Australia (KC,Occam)
Günther HotzUniversität Saarbrücken, Germany (AIT,CC)
Marcus HutterAustralian National University, Australia (AIT,AP,AI,ML)
Yuri KalnishkanRoyal Holloway University of London, UK (AIT,ML)
Bjorn Kjos-HanssenUniversity of Connecticut, Storrs, CT, USA (AR)
Andrei KolmogorovMoscow, Russia (AIT)
Kevin KorbMonash University, Melbourne, Australia (MDL)
Sophie LaplanteUniversité Paris-Sud, France (CC,KC,AR)
Tor LattimoreAustralian National University, Australia (AIT,AP,ML)
Troy LeeCWI Amsterdam, The Netherlands (CC,KC)
Leonid A. LevinBoston University, USA (AIT)
Ming LiUniversity of Waterloo, Canada (AIT)
Luc LongpréUniversity of Texas at El Paso, USA (KC,CC)
Jack LutzIowa State University, USA (AR)
Jean-Yves MarionLORIA Université Nancy, France (CC,KC)
Per Martin-LöfUniversity of Stockholm, Sweden (AR)
Elvira MayordomoUniversity of Zaragossa, Spain (AR)
Wolfgang MerkleUniversität Heidelberg, Germany (AR)
Nenad MihailovicUniversität Heidelberg, Germany (AR)
Joseph MillerUniversity of Wisconsin—Madison, USA (CC,KC,AR)
Philippe MoserIowa State University, USA (AR)
Andrej MuchnikInstitute of New Technologies, Moscow, Russia (AIT)
Andre NiesUniversity of Auckland, New Zealand (AR)
Jan PolandIstituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano (AIT,ML)
Jan ReimannUniversität Heidelberg, Germany (KC,AR)
Jorma RissanenAlmaden Research Center, San Jose, CA, USA (MDL)
Andrei RomashchenkoInstitute of Problems of Information Transmission, Moscow, Russia (KC)
Boris RyabkoSiberian State University of Telecommunication and Computer Science, Siberia (AR,KC)
Jürgen SchmidhuberIstituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (US,AIT,ML)
Claus-Peter SchnorrGoethe-Universität Frankfurt, Germany (AR)
Robert SolovayUniversity of California, Berkeley, USA (AIT)
Alexander Kh. ShenInstitute of Problems of Information Transmission, Moscow, Russia (CC,AIT)
Theodor A. SlamanUniversity of California, Berkeley, USA (AR,CC)
Ray J. SolomonoffOxbridge Research, Cambridge, MA, USA (AP,ML,AI)
Ludwig StaigerUniversität Halle, Germany (AR)
Frank StephanUniversität Heidelberg, Germany (AR)
Sebastiaan A. TerwijnTechnical University of Vienna, Austria (AR)
Leen TorenvlietUniversity of Amsterdam, The Netherlands
Boris A. TrakhtenbrotTel Aviv University, Israel
John TrompCWI Amsterdam, The Netherlands (CC,KC)
Maxim UshakovMoscow State University, Russia
Vladimir UspenskyMoscow State University, Russia
Vladimir V'yuginInstitute of Problems of Information Transmission, Moscow, Russia (KC)
Michael VyuginRoyal Holloway University, London, UK (KC,ML)
Nikolai VereshchaginMoscow State University, Russia (KC,CC)
Paul M. B. VitanyiCWI, Amsterdam, The Netherlands (KC,ML)
Volodya VovkRoyal Holloway University, London, UK (KC,ML)
Chris WallaceMonash University, Australia (MML)
Yongge WangUniversity Heidelberg, Germany (CC,AR)
Osamu WatanabeTokyo Institute of Technology, Tokyo, Japan (CC,KC)



Legacy of Ray Solomonoff

The great Ray Solomonoff, founding father of Algorithmic Information Theory, died on 7 December, 2009 at age 83, from complications in the wake of a broken aneurysm in his head. He is survived by his loving wife, Grace, and by his nephews, Alex and David.
His death has spurred various events and publications in his honor: Ray will live on in the many minds shaped by his revolutionary ideas in AI and his significant contributions to the induction problem.

Ray Solomonoff Leonid Levin

Ray Solomonoff ... Algorithmic Probability can serve as a kind of 'Gold Standard' for induction systems

Only math nerds would call 2500 finite Leonid Levin

 © 2000 by ...  home   search   science   calculators   personal   contact   up  ... Marcus Hutter