1971 dissertation of Leonid A. Levin.

I was often asked about details of some results only sketched in my published papers. So, I post here my: 1971 dissertation (in Russian) on Kolmogorov Complexity that contains many such details and its English translation (also in Arxiv.org). It was distributed in a small number of copies and only its extended abstract was published at the time and sent out to all Russian experts in the field. Russian dissertations were required to be based on work published before their submission. Thus many my related results on Kolmogorov Complexity, unpublished at the time, are not included in the dissertation. So, I supplement it with a few of my letters to A.N. Kolmogorov (and their translations published by A.Shen) describing such results. They belong to Fall 1970 - January 1971, before Kolmogorov's ocean expedition. I also add a handwritten draft of one letter a final copy of which I could not find. (I do not include materials on other topics, such as Complexity of Computation.) This was a time of my serious problems with Soviet authorities that blocked my academic carrier in Russia and forced my 1978 emigration. Thus I attach the reports (one translated ) of all reviewers of my dissertation and my Moscow University exit recommendations (the official one mentioning my lack of wisdom in speaking against party decisions :-).