home search Algorithmic Information Theory contact up

 News Future events, ... Introduction What is AIT? AIT Mailing List Introductory Material Tutorials, Information... Bibliography Books, papers... People Homepages Communication Mailing Lists Events Conferences, Workshops... Miscellaneous Courses, Info on A.K. Legacy of Ray Solomonoff Links Andrei Kolmogorov The theory of probability ... can and should be developed from axioms ... Entities should not be multiplied unnecessarily William of Occam It seems to me that the most important discovery since Gödel was the discovery by Chaitin, Solomonoff, and Kolmogorov of a concept called Algorithmic Probability. ... This is a beautiful theory ... Everybody should learn all about that and spend the rest of their lives working on it. Marvin Minsky, 2010

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) group 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.

People

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 Allender Rutgers University, New Jersey, USA (AR) Klaus Ambos-Spies Universität Heidelberg, Germany (AR) Eugene Asarin Université Joseph Fourier, Grenoble, France Luis Antunes University of Porto, Portugal (AIT) Maxim Babenko Moscow State University, Russia (KC) Janis Barzdins University of Latvia (AIT) Verónica Becher University of Buenos Aires, Argentina (AR,KC) Harry Buhrman CWI and University of Amsterdam, The Netherlands (AR,KC) Cristian S. Calude University of Auckland, New Zealand (AR) Gregory J. Chaitin IBM Research, Yorktown Heights, NY, USA (AR,AI) Alexey Chernov Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (KC,CC) Thomas Cover Stanford University, CA, USA (AIT,other) David Dowe Monash University, Melbourne, Australia (MML) Rodney G. Downey Victoria University, New Zealand (AR) Bruno Durand Université de Provence, Marseille, France Allan Erskine University College London, UK (ML,KC) Santiago Figueira University of Buenos Aires, Argentina (AR,KC) Lance Fortnow University of Chicago, USA (CC) Péter Gács Boston University, USA (AIT) Alex Gammerman Royal Holloway University, London, UK (AIT,ML) Murray Gell-Mann Santa Fe Institute, USA (AIT,other) Peter Grünwald CWI and Eindhoven University of Technology, The Netherlands (MDL) Denis R. Hirschfeldt University of Chicago, USA (AR) John Hitchcock University of Wyoming, Laramie, WY, USA (AIT,CC) Achim Hoffmann University of New South Wales, Australia (KC,Occam) Günther Hotz Universität Saarbrücken, Germany (AIT,CC) Marcus Hutter Australian National University, Australia (AIT,AP,AI,ML) Yuri Kalnishkan Royal Holloway University of London, UK (AIT,ML) Bjorn Kjos-Hanssen University of Connecticut, Storrs, CT, USA (AR) Andrei Kolmogorov Moscow, Russia (AIT) Kevin Korb Monash University, Melbourne, Australia (MDL) Sophie Laplante Université Paris-Sud, France (CC,KC,AR) Tor Lattimore Australian National University, Australia (AIT,AP,ML) Troy Lee CWI Amsterdam, The Netherlands (CC,KC) Leonid A. Levin Boston University, USA (AIT) Ming Li University of Waterloo, Canada (AIT) Luc Longpré University of Texas at El Paso, USA (KC,CC) Jack Lutz Iowa State University, USA (AR) Jean-Yves Marion LORIA Université Nancy, France (CC,KC) Per Martin-Löf University of Stockholm, Sweden (AR) Elvira Mayordomo University of Zaragossa, Spain (AR) Wolfgang Merkle Universität Heidelberg, Germany (AR) Nenad Mihailovic Universität Heidelberg, Germany (AR) Joseph Miller University of Wisconsin—Madison, USA (CC,KC,AR) Philippe Moser Iowa State University, USA (AR) Andrej Muchnik Institute of New Technologies, Moscow, Russia (AIT) Andre Nies University of Auckland, New Zealand (AR) Jan Poland Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano (AIT,ML) Jan Reimann Universität Heidelberg, Germany (KC,AR) Jorma Rissanen Almaden Research Center, San Jose, CA, USA (MDL) Andrei Romashchenko Institute of Problems of Information Transmission, Moscow, Russia (KC) Boris Ryabko Siberian State University of Telecommunication and Computer Science, Siberia (AR,KC) Jürgen Schmidhuber Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (US,AIT,ML) Claus-Peter Schnorr Goethe-Universität Frankfurt, Germany (AR) Robert Solovay University of California, Berkeley, USA (AIT) Alexander Kh. Shen Institute of Problems of Information Transmission, Moscow, Russia (CC,AIT) Theodor A. Slaman University of California, Berkeley, USA (AR,CC) Ray J. Solomonoff Oxbridge Research, Cambridge, MA, USA (AP,ML,AI) Ludwig Staiger Universität Halle, Germany (AR) Frank Stephan Universität Heidelberg, Germany (AR) Sebastiaan A. Terwijn Technical University of Vienna, Austria (AR) Leen Torenvliet University of Amsterdam, The Netherlands Boris A. Trakhtenbrot Tel Aviv University, Israel John Tromp Formerly at the Dutch Centre for Math&CS and CWI, The Netherlands (CC,KC) Maxim Ushakov Moscow State University, Russia Vladimir Uspensky Moscow State University, Russia Vladimir V'yugin Institute of Problems of Information Transmission, Moscow, Russia (KC) Michael Vyugin Royal Holloway University, London, UK (KC,ML) Nikolai Vereshchagin Moscow State University, Russia (KC,CC) Paul M. B. Vitanyi CWI, Amsterdam, The Netherlands (KC,ML) Volodya Vovk Royal Holloway University, London, UK (KC,ML) Chris Wallace Monash University, Australia (MML) Yongge Wang University Heidelberg, Germany (CC,AR) Osamu Watanabe Tokyo 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 ... 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