(Guest Post by Alexander Shen. Thanks to Lance for
Suggesting it.)

Andrej (Andrey) Muchnik died unexpectly last March, but the news
didn't spread out, so I am thankful to Lance Fortnow and Bill Gasarch
who give me the opportunity to write a few words about him. His death
was a sudden blow not only for his family (his parents, Albert A.
Muchnik, of Muchnik - Friedberg solution of Post problem, and
Nadezhda M. Ermolaeva; both were students of Petr S. Novikov; and his
brother Ilya) but also for all his colleagues.

Andrej, whom I knew since our undergraduate studies, was not only the
brilliant mathematician, but a deep thinker. He lived in his own
world -- a very rich one that was not completely unrelated to a "real
life" (i.e., the mess around us), but still clearly separated from
it, and the interactions between these two worlds were quite
difficult and often painful. His mathematical interests were driven
by internal logic of the subject, not the current "fashion";
sometimes he rediscovered an old result not knowing about it; at some
other times his results (being not published or published only in a
short note) were rediscovered later by others. Probably his most
known result is an elementary proof of Rabin's theorem (decidability
of second-order monadic theory of two successors), invented while
Andrej was a fourth-year student, and its generalizations; my
personal favourite is one of his last results saying that for any
strings A and B there is a string C such that |C| [length] is about K
(A|B) [conditional Kolmogorov complexity]; K(C|A) is negligible and K
(A|B,C) is negligible (all up to logarithmic terms).

a seminar in Moscow that was started by Kolmogorov himself;
the work of this seminar and its participants was deeply influenced
by Andrej, and I think that all we agree that most non-trivial ideas
discussed in this seminar and most interesting results obtained by
the participants of the seminar were due to Andrej (or at least
inspired by him). Personally I am extremely grateful to him for all
his support and encouragement and very sorry that I didn't tell this
to him explicitly and didn't help him enough while he was alive.

See the seminar site note (both Russian and English) (written mostly by Andrej's teacher and
friend, how helped him a lot, Alexey Semenov)

some papers of Andrej (not all -- we are still trying to prepare some
unfinished papers for publication)
can be found
here

Please update the links in the post, they were changed to be shorter.

ReplyDeleteAndrej Muchnik's Memorial Page

Seminar site note

Preliminary list of papers