Новосибирский государственный университет

Факультет информационных технологий

Современные проблемы информатики и вычислительной техники

ICT SBRAS
А.М.Федотов

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

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

[Пост]

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

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

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

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

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

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

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


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

|Головная| |Преподавание| | Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотов Анатолий Михайлович
[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 1998-2019, Новосибирский государственный университет, Новосибирск
© 1998-2019, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2019, Федотов А.М.
    Дата последней модификации: 29.11.2013