Эмиль Леон Пост ( / poʊ st / ; 11 февраля 1897 — 21 апреля 1954) — американский математик и логик . Он наиболее известен своими работами в области, которая в конечном итоге стала известна как теория вычислимости .
Пост родился в Августове , Сувальская губерния , Конгресс Польши , Российская империя (ныне Польша) в польско-еврейской семье, иммигрировавшей в Нью-Йорк в мае 1904 года. Его родителями были Арнольд и Перл Пост. [2]
Пост интересовался астрономией, но в возрасте двенадцати лет потерял левую руку в автокатастрофе. Эта потеря стала серьезным препятствием на пути к карьере профессионального астронома, что привело к его решению заняться математикой, а не астрономией. [3]
Пост учился в средней школе Таунсенда Харриса и в 1917 году окончил Городской колледж Нью-Йорка со степенью бакалавра математики. [1]
После получения докторской степени. Получив степень доктора математики в 1920 году в Колумбийском университете под руководством Кассиуса Джексона Кейзера , он получил докторскую степень в Принстонском университете в 1920–1921 учебном году. Затем Пост стал учителем математики в средней школе в Нью-Йорке.
Пост женился на Гертруде Сингер в 1929 году, от которой у него родилась дочь Филлис Пост Гудман (1932–1995). [4] Пост тратил не более трех часов в день на исследования по совету своего врача, чтобы избежать маниакальных приступов, которые он испытывал с года обучения в Принстоне. [5]
В 1936 году его назначили на математический факультет Городского колледжа Нью-Йорка. Он умер в 1954 году от сердечного приступа после лечения электрошоком от депрессии ; [5] [6] ему было 57 лет.
В своей докторской диссертации, позднее сокращенной и опубликованной как «Введение в общую теорию элементарных предложений» (1921), Пост доказал, среди прочего, что исчисление высказываний Principia Mathematica было полным: все тавтологии являются теоремами , учитывая аксиомы Principia Mathematica. а также правила замены и modus ponens . Пост также разработал таблицы истинности независимо от К.С. Пирса и Людвига Витгенштейна и нашел им хорошее математическое применение. В известном справочнике Жана ван Хейеноорта по математической логике (1966) перепечатана классическая статья Поста 1921 года, излагающая эти результаты.
Находясь в Принстоне, Пост был очень близок к открытию неполноты Principia Mathematica , которую Курт Гёдель доказал в 1931 году. Первоначально Пост не смог опубликовать свои идеи, поскольку считал, что для их принятия ему необходим «полный анализ». [2] Как сказал Пост в открытке Гёделю в 1938 году:
В 1936 году Пост независимо от Алана Тьюринга разработал математическую модель вычислений, которая по сути была эквивалентна модели машины Тьюринга . Задумав это как первую из серии моделей эквивалентной мощности, но возрастающей сложности, он назвал свою статью « Формула 1» . Эту модель иногда называют «машиной Поста» или машиной Пост-Тьюринга , но ее не следует путать с машинами тегов Поста или другими специальными видами канонической системы Поста , вычислительной моделью, использующей переписывание строк и разработанной Постом в 1920-х годах, но сначала опубликовано в 1943 году. Техника переписывания Поста в настоящее время повсеместно используется в спецификациях и проектировании языков программирования, и поэтому лямбда -исчисление Чёрча оказывает заметное влияние классической современной логики на практические вычисления. Пост разработал метод «вспомогательных символов», с помощью которого он мог канонически представлять любой постгенеративный язык, а также любую вычислимую функцию или множество вообще.
Системы соответствия были введены Постом в 1946 году, чтобы дать простые примеры неразрешимости . [8] Он показал, что проблема соответствия Поста (PCP) удовлетворения их ограничений, вообще говоря, неразрешима. Неразрешимость проблемы соответствия оказалась именно тем, что было необходимо для получения результатов о неразрешимости в теории формальных языков .
Во влиятельном обращении к Американскому математическому обществу в 1944 году он поднял вопрос о существовании невычислимого рекурсивно перечислимого множества , степень Тьюринга которого меньше, чем у проблемы остановки . Этот вопрос, ставший известным как проблема Поста , стимулировал множество исследований. Она была решена положительно в 1950-х годах благодаря введению мощного метода приоритетов в теории вычислимости .
Пост внес фундаментальный и до сих пор влиятельный вклад в теорию полиадических, или n -арных, групп в длинной статье, опубликованной в 1940 году . Его основная теорема показала, что полиадическая группа — это итеративное умножение элементов нормальной подгруппы группы. , такой, что факторгруппа является циклической порядка n - 1. Он также продемонстрировал, что полиадическая групповая операция на множестве может быть выражена через групповую операцию на том же множестве. В статье содержится много других важных результатов.