17 Dec
2003
17 Dec
'03
11:17 p.m.
Program-length complexity is well-studied in the literature. A good introductory paper is ``A Theory of Program Size Formally Identical to Information Theory'' by G. J. Chaitin, _Journal of the ACM_, 22 (1975) reprinted in Chaitin's book _Information Randomness & Incompleteness_, World Scientific Publishing Co., 1990.
The Li+Vitanyi chapter in the _Handbook of Theoretical Comp. Sci_, Vol. A, is a nice review. And your library probably has the book, while it may not have their new text.
John E. Kreznar
Eli ebrandt@jarthur.claremont.edu PGP 2 key by finger or e-mail "Your hideous criminal clock, your insidious time bomb, is tick-tick-ticking." -- L. Detweiler