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

Пост (Post) Эмиль Леон (1

1. 2.1897, Августов, Польша, ≈ 2

   1. 4,1954, Нью-Йорк), американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-Иоркском и др. университетах США. Им получен ряд фундаментальных результатов в математической логике ; одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем ( исчислений ); доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний; изучение систем многозначной логики с более чем 3 значениями истинности; одно из первых (независимое от А. М. Тьюринга ) определении понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировка основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения; результаты о выразимости общерекурсивных функций и предикатов через примитивно рекурсивные, в частности т. н. теорема о нормальной форме; первые (одновременно с А. А. Марковым ) доказательства алгоритмической неразрешимости ряда проблем математической логики и алгебры и др.

      Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957 (имеется лит.).