Albert Abramovich Muchnik (2 de enero de 1934 - 14 de febrero de 2019) fue un matemático ruso que trabajó en el campo de los fundamentos y la lógica matemática .
Recibió su doctorado del Instituto Pedagógico Estatal de Moscú en 1959 bajo la supervisión de Pyotr Novikov . Desde allí, escribió su disertación titulada Solución al problema de postreducibilidad. [1] La contribución más significativa de Muchnik fue sobre el tema de la computabilidad relativa . Él y Richard Friedberg introdujeron independientemente el método de prioridad que dio una respuesta afirmativa al problema de Post con respecto a la existencia de grados de Turing recursivamente enumerables entre 0 y 0' . Este resultado, ahora conocido como el teorema de Friedberg-Muchnik , [2] [3] abrió el estudio de los grados de Turing de los conjuntos recursivamente enumerables que resultaron poseer una estructura muy complicada y no trivial.
Muchnik también hizo contribuciones significativas a la teoría de problemas de masas de Medvedev, introduciendo una generalización de los grados de Turing, llamados "grados de Muchnik", en 1963. [4] Muchnik también elaboró la propuesta de Kolmogorov de ver el intuicionismo como "cálculo de problemas" y demostró que la red de grados de Muchnik es brouweriana .
Muchnik estuvo casado con la matemática rusa Nadezhda Ermolaeva. Su hijo Andrey Muchnik , que murió en 2007, también fue matemático y trabajó en los fundamentos de las matemáticas. [5] Albert Muchnik murió en febrero de 2019.