Andrey Muchnik

Andrey Albertovich Muchnik (February 24, 1958 - March 18, 2007) was a Soviet and Russian mathematician who practiced mathematical logic. He was awarded the A. N. Kolmogorov Prize in 2006.

Biography Andrey Muchnik was born on February 24, 1958, in the Soviet Union. His parents were Albert Abramovich Muchnik and Nadezhda Mitrofanovna Ermolaeva. Both of his parents were mathematicians and students of P. S. Novikov, a Soviet mathematician. Muchnik's father, Albert Muchnik, solved Post's problem regarding the existence of a non-trivial enumerable degree of Turing reducibility.

Andrey Muchnik began his academic journey at Moscow State University. Muchnik began working as a mathematician at the seminar of Evgenii Landis and Yulij Ilyashenko for third year students of the Faculty of Mechanics and Mathematics of Lomonosov Moscow State University. In his second year, he published his first work on differential equations under the guidance of Ilyashenko.

Starting in his third year, he specialized in definability theory at the Department of Mathematical Logic, under the supervision of Alexei Semenov. In 1981, he completed his diploma on the solution to a problem posed by Michael Rabin at the International Congress of Mathematicians in Nice. The problem involved eliminating transfinite induction in the proof of Rabin's theorem on the solvability of the monadic theory of infinite trees. Later on, Muchnik applied his approach to prove a generalization of Rabin's theorem, which had been announced by Shelah and Stupp. Using the original idea of Alfred Tarski, he introduced in the notion of self-definability to derive a proof of the Cobham-Semenov theorem. He earned his Ph.D. in 2001.

Subsequently, he worked at the Institute of New Technologies and the Scientific Council of the USSR Academy of Sciences in the field of cybernetics. He eventually became one of the leaders of the Kolmogorov seminar at Moscow State University.

Muchnik also contributed results to the field of algorithmic information theory. Many of his results and collaborations were published after his death.

Awards Andrey Muchnik was awarded the A.N. Kolmogorov Prize (along with Alexei Semenov, 2006) for his work in the field of mathematics and for the series of works "On the Refinement of A.N. Kolmogorov, Related to the Theory of Chance.”