2003: Kolmogorov's 100th birthday. Selected Kolmogorov events:

Kolmogorov centennial (2003)

Kolmogorov meeting at Dagstuhl (2003)

Latest Kolmogorov meeting at Dagstuhl (2006)

Believe it or not - Kolmogorov complexity theory is also relevant for explaining the entire universe! Check out our work on minimal digital physics.

Also check out the complexity-based theory of beauty!

The algorithmic information or Kolmogorov complexity of a bitstring x is the length of the shortest program that computes x and halts. This is one of the fundamental concepts of theoretical computer science. Follow this link to the Kolmogorov mailing list home page at IDSIA.

What if we allow for nonhalting computations on nonstandard Turing machines? It turns out that some things then become much more compactly describable. This leads to generalizations of the concept of Kolmogorov complexity, and has consequences for Solomonoff's theory of algorithmic probability and universal prediction. It also leads to "Super Omegas" that are computable in the limit - generalizations of Chaitin's halting probability Omega of a Turing machine with random input.
.

J. Schmidhuber. Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612 (2002). PS. PDF. Flawed HTML (knowledge of LATEX helps). Based on sections 2-5 of TR IDSIA-20-00, Version 2.0: Algorithmic Theories of Everything, PDF. Dec 20, 2000 (515K, 50 pages, 10 theorems, 100 refs). HTML. Also in the physics arXiv: quant-ph/ 0011122. Overview.
.

Letter on what's random in physics (Nature 439, 392, 26 Jan 2006)

Related machine learning work led to procedures for finding low-complexity neural networks matching given training data:

J. Schmidhuber. Discovering neural nets with low Kolmogorov complexity and high generalization capability. Neural Networks, 10(5):857-873, 1997. PS.GZ. PDF. HTML.

J. Schmidhuber. Discovering solutions with low Kolmogorov complexity and high generalization capability. In Proc. ICML'95, pages 488-496. Morgan Kaufmann, San Francisco, CA, 1995. PS.GZ. PDF. HTML.

More recent work of 2013: Compressed Network Search Finds Complex Neural Controllers with a Million Weights, learns to drive without a teacher from raw high-dimensional video input

Abstract of IJFCS paper: The traditional theory of Kolmogorov complexity and algorithmic probability focuses on monotone Turing machines with one-way write-only output tape. This naturally leads to the universal enumerable Solomonoff-Levin measure. Here we introduce more general, nonenumerable but cumulatively enumerable measures (CEMs) derived from Turing machines with lexicographically nondecreasing output and random input, and even more general approximable measures and distributions computable in the limit. We obtain a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity, suggesting that the ``true'' information content of some (possibly infinite) bitstring x is the size of the shortest nonhalting program that converges to x and nothing but x on a Turing machine that can edit its previous outputs. Among other things we show that there are `Super Omegas' computable in the limit yet more random than Chaitin's ``number of wisdom'' Omega, that any approximable measure of x is small for any x lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of x is small for any x lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.

More recent paper on this topic (2006): A. Chernov, J. Schmidhuber. Prefix-like Complexities and Computability in the Limit. Proc. of Second Conference on Computability in Europe, CiE 2006, LNCS 3988, pp. 85-93. Based on TR IDSIA-11-05: PDF.
Abstract: Generalized Turing machines (GTMs) are a variant of non-halting Turing machines, by computational power similar to machines with the oracle for the halting problem. GTMs allow a definition of a kind of descriptive (Kolmogorov) complexity that is uniform for finite and infinite sequences. There are several natural modifications of the definition (as there are several monotone complexities). This paper studies these definitions and compares complexities defined with the help of GTMs and complexities defined with the help of oracle machines.

Summer 2004: Jan Poland (IDSIA) proves perfect coding theorem for enumerable output machines, by redefining EOM complexity and adapting Schmidhuber's proof (IJFCS 2002).

Abstract: Recently, Schmidhuber proposed a new concept of generalized algorithmic complexity. It allows for the description of both finite and infinite sequences. The resulting distributions are true probabilities rather than semimeasures. We clarify some points for this setting, concentrating on Enumerable Output Machines. As our main result, we prove a strong coding theorem (without logarithmic correction terms), which was left as an open problem. To this purpose, we introduce a more natural definition of generalized complexity.

J. Poland. A coding theorem for enumerable output machines. Information Processing Letters 91(4):157-161, 2004.

Communicated by P. M. B. Vitanyi; available online as preprint IDSIA-05-04: PDF

There even is an art form based on short programs: Low-Complexity Art.