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

Альберт Абрамович Мучник
Фотография на заседании семинара кафедры математической логики
Дата рождения	2 января 1934(1934-01-02)
Дата смерти	14 февраля 2019(2019-02-14) (85 лет)
Место смерти	Москва
Страна	Россия
Род деятельности	математик
Научная сфера	математика
Место работы	ИПМ им. Келдыша
Альма-матер	МГПИ
Учёная степень	кандидат физико-математических наук
Научный руководитель	Пётр Сергеевич Новиков
Ученики	Алексей Львович Семёнов

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

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

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

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

Учеником Ал. А. Мучника был Алексей Львович Семёнов, научный руководитель его старшего сына, Андрея Альбертовича Мучника (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

• Мучник, Альберт Абрамович на математическом портале Math-Net.Ru

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (26 марта 2019)