Albert Abramovich Muchnik (2 January 1934 – 14 February 2019) was a
Russian
Russian(s) refers to anything related to Russia, including:
*Russians (, ''russkiye''), an ethnic group of the East Slavic peoples, primarily living in Russia and neighboring countries
*Rossiyane (), Russian language term for all citizens and peo ...
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
who worked in the field of foundations and
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
.
He received his Ph.D. from
Moscow State Pedagogical Institute
Moscow State Pedagogical University or Moscow State University of Education is an educational and scientific institution in Moscow, Russia, with eighteen faculties and seven branches operational in other Russian cities. The institution had underg ...
in 1959 under the advisorship of
Pyotr Novikov
Pyotr Sergeyevich Novikov (russian: Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician.
Novikov is known for his work on combinatorial proble ...
. Muchnik's most significant contribution was on the subject of
relative computability. He and
Richard Friedberg independently introduced the priority method which gave an affirmative answer to
Post's problem
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
regarding the existence of
recursively enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
Turing degrees between 0 and 0' . This result, now known as the
Friedberg–Muchnik theorem In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. It is a more general view of the Kleene–Post theorem. T ...
, opened study of the Turing degrees of the recursively enumerable sets which turned out to possess a very complicated and non-trivial structure.
Muchnik also made significant contributions to Medvedev's theory of mass problems, introducing a generalisation of Turing degrees, called "Muchnik degrees", in 1963. Muchnik also elaborated
Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
's proposal of viewing
intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...
as "calculus of problems" and proved that the lattice of Muchnik degrees is
Brouwerian.
Muchnik was married to the Russian mathematician Nadezhda Ermolaeva. Their son Andrej, who died in 2007, was also a mathematician working in foundations of mathematics.
[S. I. Adian, A. L. Semenov, V. A. Uspenskii]
''Andrei Albertovich Muchnik''
Uspekhi Matematicheskikh Nauk
''Uspekhi Matematicheskikh Nauk'' (russian: Успехи математических наук) is a Russian mathematical journal, published by the Russian Academy of Sciences and Moscow Mathematical Society and translated into English as ''Russi ...
, vol. 62 (2007), no. 4, pp. 140–144 He died in February 2019.
Selected publications
*A. A. Muchnik, ''On the unsolvability of the problem of reducibility in the theory of algorithms''.
Doklady Akademii Nauk SSSR
The ''Proceedings of the USSR Academy of Sciences'' (russian: Доклады Академии Наук СССР, ''Doklady Akademii Nauk SSSR'' (''DAN SSSR''), french: Comptes Rendus de l'Académie des Sciences de l'URSS) was a Soviet journal that ...
(N.S.), vol. 108 (1956), pp. 194–197
References
External links
Albert Mucknik's personal webpage Keldysh Institute of Applied Mathematics
The Keldysh Institute of Applied Mathematics (russian: Институт прикладной математики им. М.В.Келдыша) is a research institute specializing in computational mathematics. It was established to solve computati ...
1934 births
2019 deaths
Mathematical logicians
Russian mathematicians
Moscow State Pedagogical University alumni
{{russia-mathematician-stub