Эмиль Пост

Эмиль Пост — американский математик и логик польско-еврейского происхождения, один из основоположников теории рекурсивных функций и теории формальных языков. Внёс значительный вклад в развитие математической логики, алгоритмической разрешимости и теории вычислимости. Известен разработкой абстрактной вычислительной машины (машины Поста), а также доказательством неполноты и неразрешимости ряда формальных систем. Работы Поста заложили фундамент для последующих исследований Алана Тьюринга, Альфреда Тарского, Стивена Клини и других.

Биография

Ранние годы и образование

Эмиль Леон Пост (англ. Emil Leon Post) родился 11 февраля 1897 года в городе Августов, входившем тогда в состав Российской империи (ныне Польша), в еврейской семье. В 1904 году семья эмигрировала в США, поселившись в Нью-Йорке. Пост получил начальное образование в публичных школах, где проявил выдающиеся способности к математике. В 1913 году поступил в Городской колледж Нью-Йорка (City College of New York), который окончил с отличием в 1917 году, получив степень бакалавра.

В 1918 году он продолжил обучение в Колумбийском университете, где под руководством Кассиуса Джексона Кейзера занимался математическим анализом и математической физикой. В 1920 году Пост защитил докторскую диссертацию на тему «Введение в общую теорию элементарных пропозиций» (Introduction to a General Theory of Elementary Propositions), в которой предложил оригинальный подход к формальной логике, основанный на многозначных истинностных таблицах.

Академическая карьера

После защиты диссертации Пост получил должность преподавателя в Корнеллском университете, однако вскоре у него развилось биполярное расстройство, что потребовало длительного лечения. В 1921 году он был вынужден прервать академическую деятельность и вернуться к родителям в Нью-Йорк, где несколько лет проработал учителем математики в средней школе. Несмотря на тяжёлое состояние, Пост продолжал заниматься математическими исследованиями.

В 1927 году он вернулся в науку, получив должность ассистента профессора в Городском колледже Нью-Йорка. В 1932 году стал профессором математики. Пост работал в этом учебном заведении до конца жизни, совмещая преподавательскую деятельность с интенсивными научными изысканиями в области математической логики. В 1936 году он опубликовал одну из своих самых важных работ — «Финитные комбинаторные процессы — формулировка 1» (Formulation 1 of Finite Combinatory Processes), в которой независимо от Алана Тьюринга предложил концепцию абстрактного вычислительного устройства, позже названного машиной Поста.

Последние годы и смерть

В 1940-х годах Пост активно занимался проблемами разрешимости и доказательствами неполноты. В 1941 году он опубликовал работу «Просто неразрешимая проблема» (A Very Unsolvable Problem), а в 1944 году — статью «Рекурсивно перечислимые множества и проблема разрешения» (Recursively Enumerable Sets and the Decision Problem), которая стала классической в теории рекурсивных функций.

Эмиль Пост страдал от тяжёлого психического расстройства, что привело к нескольким госпитализациям. 21 апреля 1954 года, находясь в состоянии сильной депрессии, он покончил с собой, совершив электрошок в своей лаборатории в Нью-Йорке.

Научный вклад

Многозначная логика

В своей докторской диссертации (1920) Пост независимо от Яна Лукасевича разработал основы многозначной логики. В отличие от классической двузначной логики (истина/ложь), Пост предложил логику с любым конечным числом истинностных значений, что широко используется в компьютерных науках, искусственном интеллекте и нечёткой логике.

Машина Поста

В 1936 году, за год до публикации Аланом Тьюрингом своей работы о «машине Тьюринга», Пост независимо предложил абстрактную вычислительную машину, которая позднее получила название «машина Поста». Она состоит из бесконечной ленты, разделённой на ячейки, каждая из которых может содержать метку или быть пустой, и головки, способной перемещаться по ленте. Машина Поста стала одной из первых формальных моделей алгоритмов и внесла вклад в доказательство Тьюринга о неразрешимости проблемы остановки.

Пост также сформулировал знаменитый тезис (известный как тезис Клини — Поста), который параллельно с тезисом Чёрча — Тьюринга утверждает, что любая интуитивно вычислимая функция может быть реализована на машине Поста или на машине Тьюринга. Однако Пост настаивал на необходимости эмпирического обоснования таких тезисов, призывая к "финитной комбинаторной формулировке" вычислимости.

Проблема разрешения

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

Пост выдвинул гипотезу о существовании рекурсивно перечислимых множеств, не являющихся рекурсивными (так называемые «простые» множества), что привело к развитию теории степеней неразрешимости.

Проблема соответствия Поста

В 1946 году Пост сформулировал знаменитую проблему соответствия Поста (Post correspondence problem), являющуюся классическим примером алгоритмически неразрешимой задачи. Она заключается в нахождении последовательности пар слов, таких чтобы их конкатенация совпадала. Эта проблема широко применяется в теории формальных языков и программирования для доказательства неразрешимости других задач.

Известные ученики и последователи

Пост воспитал целое поколение математиков-логиков. Среди его учеников и коллег, испытавших его влияние, — Стивен Клини, Алонзо Чёрч, Алан Тьюринг, Мартин Дэвис, Баркли Россер и другие. В 1940-х годах Пост состоял в активной переписке с Куртом Гёделем, обсуждая вопросы неполноты и выразимости формальных систем.

Память

• В честь Эмиля Поста названа машина Поста и проблема соответствия Поста.
• В 1999 году в Городском колледже Нью-Йорка была учреждена именная профессура имени Поста.
• Логическое общество Post’s Revenge (названное в честь его работы «Recursive Forcing») проводит ежегодные конференции по теории рекурсивных функций.

Основные труды:

• Post, E. L. (1920). "Introduction to a General Theory of Elementary Propositions". American Journal of Mathematics.
• Post, E. L. (1936). "Finite Combinatory Processes—Formulation 1". Journal of Symbolic Logic.
• Post, E. L. (1944). "Recursively Enumerable Sets of Positive Integers and Their Decision Problems". Bulletin of the American Mathematical Society.
• Post, E. L. (1947). "Recursive Unsolvability of a Problem of Thue". Journal of Symbolic Logic.

Интересные факты

• Пост был первым математиком, который предложил идею «машины с произвольным доступом к памяти», предвосхитившей современные компьютеры.
• Диссертация Поста была написана за два месяца и сразу признана одной из самых глубоких работ по логике того времени.
• Из-за психического расстройства Пост не мог публично читать лекции в последние годы жизни; его записи передавались коллегам и студентам.

Примечания

Математические труды Поста в основном носят теоретический характер; их практическое применение связано с разработкой алгоритмов, компиляторов и систем искусственного интеллекта. Пост внёс вклад не только в математику, но и в философию — в частности, в проблему определения границ формального познания.

Источники

• Davis, M. (1972). "Emil L. Post: A Biography". Mathematical Logic Quarterly.
• Kleene, S. C. (1981). "The work of Emil L. Post". Historia Mathematica.
• "Emil L. Post". Stanford Encyclopedia of Philosophy (SEP), 2023.