[FOM] impredicative definitions/paper announcement

[Walt Read]

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:

<http://www.scholarpedia.org/article/Algorithmic_randomness>

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.

-Walt