[FOM] impredicative definitions/paper announcement

Walt Read walt.read at gmail.com
Wed Dec 1 18:30:49 EST 2010

Nick Nielsen wrote:

> What is the difference, if any, between the arbitrary and the random?
> Nick

There are a number of algorithmic approaches to randomness, depending
on what aspect of randomness you're looking at, and mostly based on
Kolmogorov-Chaitin-Solomonoff complexity. For a quick and readable
introduction, check out Downey and Reimann's page on Scholarpedia:


They list some recent books on the subject. In particular, Li and
Vitanyi <http://www.amazon.com/Introduction-Kolmogorov-Complexity-Applications-Computer/dp/0387948686>
have a very nice historical/developmental discussion as well as
technical exposition.


More information about the FOM mailing list