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

А.М.Федотов

Словарь-справочник по информатике (онтология информатики)

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

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

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

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

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

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

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

Ключевые термины:  машина тьюринга-поста;   логика;   история ИТ;

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

Федотов Анатолий Михайлович

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