From: jbaez@riesz.mit.edu (John C. Baez)
Subject: Re: Chaitin's Omega and QM (was: Bayes' theorem and QM)
Organization: MIT Department of Mathematics, Cambridge, MA
Date: Mon, 14 Dec 92 22:32:29 GMT

I salute Michael Weiss' post introducing people to the literature on 
the number Omega, algorithmic information theory, algorithmic
randomness theory etc..  This stuff is seriously cool and should be
known by all those who love beautiful ideas.  Here is a nice
bibliography of stuff along these lines that was passed on to me by Dave
DeMers.  Unfortunately is doesn't have a reference to Martin-Loef, who
(along with Kolmogorov, Solomonoff, Chaitin and others) deserves a lot
of credit.  

I quote DeMers:

For Kolmogorov Complexity in general, the best place to
start would be with
an introduction to the notions of Kolmogorov Complexity and
its application to a number of different problems which can
be found in:

Li, M.  and Paul Vitanyi, Kolmogorov Complexity and Its
Applications, in
Handbook of Theoretical Computer Science, (J. van Leeuwen, Ed.)
North-Holland, 1989.

A preliminary version of the same work is in the Proceedings
of the 3d IEEE Structure in Complexity Theory Conference, 1988.

The same authors have a book out by Addison-Wesley,
An Introduction to Kolmogorov Complexity and its Applications (1989).

For original work, see the references in the bibliography of
the above book.  Let me point out the following which
are probably most important:

Kolmogorov, AN, "Three approaches to the quantitative definition
of information" Problems in Information Transmission 1, 1-7, 1965;

Shannon & Weaver, The Mathematical Theory of Communication, U. of
Illinois Press, 1949 (for basics of information theory)

Kolmogorov, A.N. "Logical Basis for information theory and
probability theory", IEEE Trans. on Info. Theory ?? 1968 (sorry)

Solomonoff, R.J., "A formal theory of inductive inference",
Information & Control 30, 1-22 and 224-254 (1964).

Chaitin, G.J., "Randomness and Mathematical Proof"
Scientific American, 232 (May 1975), pp47-52

Chaitin, G.J., "Algorithmic Information Theory", IBM J. Res.
Dev. 21, 350-359 (1977)

Chaitin, G.J.,  Information, Randomness and Incompleteness.
(World Scientific Pub, 1987)

other surveys are:
Zvonkin, A.K. and L.A. Levin, "The complexity of finite
objects and the development of the concepts of information
and randomness by the means of the Theory of Algorithms",
Russ. Math. Survey 25, 83-124 (1970)


Schnorr, C.P., "A survey of the theory of random sequences",
in Basic Problems in Methodology and Linguistics (Butts, R.E. Ed.)
1977, pp. 193-210.


Application of Kolmogorov Complexity, or similar ideas, can
be seen in work of Valiant, Gold, Rissanen & others (maximum
likelihood, maximum entropy...).  I
might mention
Rissanen, J., "Modeling by the shortest data description",
Automatica 14, 465-471 (1978)
for a practical suggestion for statistical modeling - minimum
description length - which has two components, one essentially
computing the size of the model and the other computing the size of
the data when encoded using the theory.

APPLICATIONS:

Can state and prove Goedel's incompleteness theorem using
Kolmogorov Complexity,

Can derive a prime-number theorem, # primes less than n
is on the order of n/ (log n (log log n)^2) ,

can state and prove the pumping lemma for regular languages
in a couple of lines,

and so on...

In the neural net world, Tenorio & Lee used a variant of
Rissanen's minimum description length along with a
stochastic growth method for determining when to add
new nodes to a network (TR-EE 89-30, June 1989, Purdue University
School of Electrical Engineering)

----
I also recommed highly the works of Bennett on "logical depth".
Newsgroups: sci.physics