Новосибирский государственный университет Факультет информационных технологий Современные проблемы информатики и вычислительной техники

Персоны в коллекции "Современные проблемы информатики"

Эмиль Леон Пост

11 февраля 1897, Августов, Царство Польское — 21 апреля 1954, Нью-Йорк

Основные достижения:

Пост один из основателей многозначной логики (1921); основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.

В 1936 независимо от работ Тьюринга , Чёрча и Клини им было уточнено понятие алгоритма в терминах, как бы сегодня сказали, компьютерной программы. Пост входит в четверку великих ученых, практически одновременно осознавших возможность уточнения общего представления об алгоритме.

В 1943 Постом было впервые предложено общее понятие исчисления, имеющее фундаментальное значение для доказательства неразрешимости ряда проблем математики. В 1944 публикуется, по-видимому, наиболее влиятельная работа Поста, где в первоначальном виде излагается теория степеней неразрешимости, а в 1947 впервые в истории математики (независимо от А.А.Маркова ) был указан пример «внутриматематической» неразрешимой массовой алгоритмической проблемы, а именно проблемы А. Туэ (проблема равенства для полугрупп). Пост считал – и писал об этом К.Гёделю , – что за 15 лет до революционных гёделевских работ о неполноте, он уже имел эти теоремы, хотя и не в такой законченной форме.

Краткая биография:

Эмиль Леон Пост (Post Emil Leon) — американский математик и логик польского происхождения.

Публикации o жизни и деятельности персоны:

1. Успенский В. А., Машина Поста / Популярные лекции по математике. - М.: Наука. - 1979. - Выпуск № 54. - С. 96. - ISBN 5-02-013735-9.

Контекстный поиск: Задайте образец для поиска:
    

Федотова Ольга Анатольевна

НГУ ФИТ НГУ ИВТ СО РАН