Мучник, Альберт Абрамович

Учился и защитил диссертацию кандидата физико-математических наук в Московском государственном педагогическом институте (научный руководитель — академик Пётр Сергеевич Новиков). Ал. А. Мучник и Ричард Фридберг решили проблему Поста, независимо доказав, что существуют перечислимые неразрешимые множества, к которым не сводится по Тьюрингу проблема остановки, и, более того, существуют не сводящиеся друг к другу по Тьюрингу перечислимые множества. Метод, использованный в этом доказательстве, получил название метода приоритета и стал одним из основных средств в теории степеней перечислимых множеств, начало которой положили работы Мучника и Фридберга.

Ал. А. Мучник определил понятие слабой сводимости для массовых проблем, продолжая работы Ю. Т. Медведева, который ввёл понятие массовой проблемы и определил сильную сводимость. Соответствующие классы эквивалентности по отношению взаимной сводимости образуют решётку, которая получила название решётки Мучника (Muchnik lattice). Она является интерпретацией для интуиционистской логики.

Помимо теории вычислимости, Ал. А. Мучник получил результаты в области многозначных логик (в соавторстве с Ю. И. Яновым), теории автоматов и модальной логике (с женой, Надеждой Митрофановной Ермолаевой)

Учеником Ал. А. Мучника был Алексей Львович Семёнов, научный руководитель его старшего сына, Андрея Альбертовича Мучника (1958—2007)

1956

• Неразрешимость проблемы сводимости теории алгоритмов, Доклады АН СССР, 108(2), 194—197 (1956)

• Об отделимости рекурсивно перечислимых множеств, Доклады АН СССР, 109(1), 29-32

1958

• Решение проблемы сводимости Поста и некоторых других проблем теории алгоритмов. I. Труды Московского математического общества, том 7, 391—405 (1958) Перевод: Amer. Math. Soc. Transl. (2) 29 1963 197—215 [Доклад на ММО был сделан 16 октября 1956 года]

• Изоморфизм систем рекурсивно перечислимых множеств с эффективными свойствами. Труды Московского математического общества, том 7, 407—412 (1958) [Доклад на ММО был сделан 17 декабря 1957 года]

  [Доказано, в частности, что пары эффективно неотделимых перечислимых множеств изоморфны. Майхилл пишет в реферате в Math. Reviews: All these results and many others in the same area have been discovered since Mučnik’s work (but in ignorance of it) by R. Smullyan in his doctoral dissertation [Princeton, 1959; to be published as Theory of formal systems in Annals of Mathematics Studies]. Though it is heartening to see the common direction of recursion-theoretic research in this country and the Soviet Union, it is sad that the lack of communication between the mathematicians of the two countries has led—now for the second time—to a needless duplication of effort in this area]

1959

• А. А. Мучник — Р.Фридберг. Проблема сводимости перечислимых множеств. Математика, её преподавание, приложения и история, Матем. просв., сер. 2, 4, 1959, 233—236

  [Популярное изложение]

• Ю. И. Янов, А. А. Мучник, О существовании k-значных замкнутых классов, не имеющих конечного базиса. ДАН СССР. 1959. Т. 127. № 1. С. 44-46.

1962

• А. А. Мучник, С. Г. Гиндикин, О полноте системы ненадёжных элементов, реализующих функции алгебры логики. Доклады АН СССР, 144(5), 1007—1010 (1962)

  [Когда можно сколь угодно надёжно реализовать любую функцию, имея ненадёжные элементы одних типов и гарантированно надёжные других]

1963

• О сильной и слабой сводимости алгоритмических проблем, Сибирский математический журнал, 4, 1328—1341 Перевод: Computability, vol. 5, no. 1, pp. 49-59, 2016

1965

• О сводимости проблем разрешения перечислимых множеств к проблемам отделимости. Изв. АН СССР. Сер. матем., 29:3 (1965), 717—724

  [Нетривиальная проблема разрешения не может сводиться к проблеме отделимости перечислимых множеств; всякое перечислимое неразрешимое множество можно разбить на две неотделимые части.]

• Gindikin, S. G.; Mučnik, A. A. Solution of the problem of completeness for systems of functions of the algebra of logic with unreliable realization. (Russian) Problemy Kibernet. No. 15 1965 65-84.

1968

• The duration of the experiment that determines the structure of a finite strongly connected automaton. (Russian) Problemy Kibernet. No. 20 1968 159—171

1970

• General linear automata. (Russian) Problemy Kibernet. No. 23 1970 171—208, 303—304.

1973

• А. А. Мучник, А. Н. Маслов, Регулярные линейные и вероятностные события, Тр. МИАН СССР, 133 (1973), 149—168

1974

• Ермолаева Н. М., Мучник А. А., Модальные расширения логических исчислений типа Хао Вана. Исследования по формализованным языкам и неклассическим логикам, М.:Наука, 172—193.

1976

• Об эндоморфизмах дистрибутивных решеток и модально-временных логиках, Седьмой Всесоюзный симпозиум по логике и методологии науки. Тезисы сообщений, Киев: Наукова Думка, 1976, 128—130.

• Ермолаева Н. М., Мучник А. А., Модальные логики, определяемые эндоморфизмами дистрибутивных решеток. Исследования по теории множеств и неоклассическим логикам, М.:Наука, 229—246

1979

• Ермолаева Н. М., Мучник А. А., Предтабличная временная логика. Исследования по неклассическим логикам и теории множеств, М.:Наука, 288—297

• Ермолаева Н. М., Мучник А. А., Функционально замкнутые 4-значные расширения булевой алгебры и соответствующие логики. Исследования по неклассическим логикам и теории множеств, М.:Наука, 298—315

1985

• Ermolaeva, N. M.; Muchnik, A. A. Functional expressibility in some tabular modal logics. (Russian) Semiotics and information science, No. 25, 94-119, 154, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1985.

• Об S5-T-Y логиках, Препринт ИПМ им. М. В. Келдыша, 2007, 086