Еміль Пост

Еміль Леон Пост
пол. Emil Leon Post
Ім'я при народженні	пол. Emil Leon Post
Народився	11 лютого 1897(1897-02-11)[…] Августув, тодішня Російська імперія, сьогодні Польща
Помер	21 квітня 1954(1954-04-21)[…] (57 років) Нью-Йорк, США
Поховання	Маунт-Геброн
Громадянство	США
Діяльність	математик, філософ, логік, викладач університету
Галузь	математика
Alma mater	Колумбійський університет
Науковий керівник	Cassius Jackson Keyserd
Знання мов	англійська
Заклад	Сіті Коледж, Принстонський університет, Колумбійський університет, Корнелльський університет і George Washington Educational Campusd
Magnum opus	Проблема збіжності Поста, Post's inversion formulad, Критерій Поста, Критерій Поста і Числення Поста
Медіафайли у Вікісховищі

Еміль Леон Пост (пол. Emil Leon Post) (11 лютого 1897, Августув, Царство Польське — 21 квітня 1954, Нью-Йорк) — американський математик та логік польського походження, один із засновників багатозначної логіки; основні праці з математичної логіки: алгебра Поста, класи Поста функцій алгебри логіки; запропонував абстрактну обчислювальну машину — машину Поста. Найбільш відомий своїми досягненнями у теорії рекурсії.

Біографія

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

У дитячому віці Еміль захоплювався астрономією, проте нещасний випадок перекреслив плани хлопця — у 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.

Див. також

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