Еміль Пост

Еміль Леон Пост народився в ортодоксальній єврейській родині, яка мешкала недалеко від Білостока. Цього ж року його батько Арнольд емігрував до Сполучених Штатів. Коли у батька справи стали йти добре, тоді сім'я (семирічний Еміль, його дві сестри і мати) теж переїхала з Царської Росії до Нью-Йорка. Сім'я мешкала у комфортабельному будинку у Гарлемі.

У дитячому віці Еміль захоплювався астрономією, проте нещасний випадок перекреслив плани хлопця — у 12-річному віці він втратив ліву руку. Перед закінченням школи Еміль подав запит у кілька обсерваторій — чи його вада не зашкодить професії астронома. Отримані відповіді утримали його від реалізації дитячих амбіцій і Еміль зайнявся математикою.

У 1921 році Еміль Пост захистив докторську дисертацію у галузі математики у Колумбійському університеті. У дисертації він виклав метод оцінки пропозиційних формул за допомогою таблиць істинності. У ній вперше отримано низку фундаментальних результатів в металозіці для класичної логіки висловлювань: несуперечність, дедуктивна повнота, розв'язність, функціональна повнота. У цій роботі вперше побудована багатозначна логіка більш ніж з 3 істинними значеннями і з довільною кількістю виділених значень. Тут же встановлено, що множина замкнутих класів у класичній логіці лічильна.

1920—1921 навчальний рік Пост провів на постдокторських студіях у Принстонському університеті. Саме тут у нього стався перший напад маніакально-депресивного психозу. Ця хвороба супроводжувала Поста протягом всього його життя. Він достатньо відновився після цього першого нападу і отримав посаду викладача у Корнельському університеті, проте другий напад змусив його припинити викладання в Університеті. Впродовж 20-х років Еміль Пост заробляв на життя викладаючи математику у George Washington High School у Нью-Йорку. Зі своїм лікарем Пост розробив режим, який був призначений унеможливити стороннє збудження, яке вело до нападів психозу. Режим дозволяв Посту займатися наукою і дослідами лише три години на день.

Незважаючи на такий режим та велике навчальне навантаження (16 годин на тиждень) Пост зміг у цей період опублікувати свої найвпливовіші праці. Його одруження з Ґертрудою Сінґер у 1929, безсумнівно, допомогло стабілізувати його життя. Дружина асистувала Емілю, друкуючи його статті та листи, а також займалася щоденними фінансами сім'ї.

У 1932 році Еміля Поста було призначено на факультет математики Сіті Коледжу в Нью-Йорку. Пропрацювавши місяць, він залишив посаду, проте, повернувся у 1935 році, і залишався на посаді до самої смерті у 1954 році від серцевого нападу під час електрошоку.

Е.Пост входить у четвірку великих учених, які практично одночасно усвідомили можливість уточнення загального уявлення про алгоритм. У 1943 Постом було вперше запропоновано загальне поняття обчислення, яке має фундаментальне значення для доведення нерозв'язності низки проблем математики. У 1944 публікується, мабуть, найвпливовіша робота Поста, де у первісному вигляді викладається теорія ступенів нерозв'язності, а у 1947 вперше в історії математики (незалежно від А А. Маркова) було наведено приклад «внутріматематичної» нерозв'язної масової алгоритмічної проблеми, а саме проблеми А. Туе (проблема рівності для напівгруп). Пост вважав — і писав про це Курту Ґеделю, — що за 15 років до революційних ґеделевських робіт про неповноту, він вже мав ці теореми, хоча і не у такій завершеній формі.

• Паралельно з А. Тюринґом ввів (і вперше — у 1936 році — опублікував) уточнене поняття алгоритму у вигляді абстрактної обчислювальної машини. Сьогодні такі абстрактні «машини» дещо несправедливо називаються машинами Тюринґа, рідше машинами Тюринґа-Поста або машинами Поста-Тюринґа.
• Є родоначальником алгебри логіки. Повністю дослідив пропозиційну логіку, яка розглядається як система (алгебра) пропозиційних функцій, зокрема описав всі її підалгебри.
• Ввів гранично загальне поняття канонічного числення, яке узагальнює поняття логічного числення у випадку систем, в яких відбуваються будь-які дискретні процеси. Теорія канонічних числень є одночасно узагальненням і логічного синтаксису, і теорії алгоритмів, оскільки алгоритми також є частковим випадком канонічних числень (інший варіант цієї ж теорії запропонував Р. М. Смалліан, увівши як первинне поняття формальної системи).

• 1936, «Finite Combinatory Processes — Formulation 1,» Journal of Symbolic Logic 1: 103—105.
• 1940, «Polyadic groups», Transactions of the American Mathematical Society 48: 208—350.
• 1943, «Formal Reductions of the General Combinatorial Decision Problem», American Journal of Mathematics 65: 197—215.
• 1944, «Recursively enumerable sets of positive integers and their decision problems», Bulletin of the American Mathematical Society 50: 284—316. Вводить важливе поняття редукції many-one.

• Машина Поста
• Числення Поста
• Багатозначна зводимість