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
translation (also in
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
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 :-).