Nothing can surpass the Li and Vitányi book in both readability and comprehensiveness, but that is a significant undertaking, and you might need alternatives. "A Short Introduction to Kolmogorov Complexity" by Volker Nannen, true to its title, is only 7 pages long. The Wikipedia page on Kolmogorov Complexity is quite good. Gregory Chaitin's Exploring Randomness is a fun, quirky, personalized view of the field, emphasizing his own work and LISP programs. Caveat: his philosophical musings are quite controversial. In fact, reading the balanced AMS review of his book by Panu Raatikainen might serve as a introduction to the area.

Nothing can surpass the Li and Vitányi book in both readability and comprehensiveness, but that is a significant undertaking, and you might need alternatives. "A Short Introduction to Kolmogorov Complexity" by Volker Nannen, true to its title, is only 7 pages long. The Wikipedia page on Kolmogorov Complexity is quite good. Gregory Chaitin's Exploring Randomness is a fun, quirky, personalized view of the field, emphasizing his own work and LISP programs. Caveat: his philosophical musings are quite controversial. In fact, reading the balanced Notices of the AMS review of his book by Panu Raatikainen might serve as a useful introduction to the area.