Randomness and Probability—Complexity of Description
Péter Gács · Encyclopedia of Statistical Sciences · 2004
At this time (1986), no easily readable, up-to-date overview of AIT is available. The most recent, fairly comprehensive work, that of Levin [(21)], can be recommended only to devoted readers. The work by Levin and Zvonkin [(23)] is comprehensive and readable but not quite up to date. The surveys by Schnorr [(26, 27)] and Chaitin [(7)] can be used to complement it. AIT created many interesting problems of its own; see, for example, Chaitin [(5, 6)], Gács [(10-12)], Levin [(22)], Loveland [(24)], Solovay [(32)], and Schnorr [(26, 28)], and the technically difficult results in Solovay [(33)] and V'iugin [(35)].