Эмиль Пост
Подробнее
- Родился
- Умер
- Известен как
- Продукционные системы, проблема соответствий, таблицы истинности
- Гражданство
- США (родом из Польши)
Логик, сформулировавший вычислимость независимо от Тьюринга, в том же году, и оказавшийся первой половиной названия «машина Поста — Тьюринга».
Эмиль Леон Пост родился в Августове в тогдашней Российской Польше и вырос в Нью-Йорке. Его диссертация 1921 года ввела таблицу истинности как метод и доказала полноту исчисления высказываний; в неопубликованных заметках того же периода он подобрался и к чему-то близкому теореме Гёделя о неполноте — за десять лет до самого Гёделя. Бумаги он убрал в стол.
В 1936 году вышла статья Finite Combinatory Processes — Formulation 1: работник перемещается вдоль бесконечного ряда ячеек и отмечает или стирает метки по списку инструкций. Модель по сути тьюринговская, придуманная без знакомства с ней, и отличается главным образом тем, что Пост описал её как человека, выполняющего приказы. Затем появились продукционные системы (1943), легшие в основу формальных грамматик, и проблема соответствий (1946) — неразрешимая задача, настолько простая, что формулируется на салфетке, а потому стандартное оружие в доказательствах неразрешимости.