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

Эмиль Леон Пост
Рожденный	11 февраля 1897 г. Августов , Сувальская губерния , Конгресс Польши , Российская империя (ныне Польша)
Умер	21 апреля 1954 г. 1954-04-21 ) (57 лет) ( Нью-Йорк, США
Альма-матер	Городской колледж Нью-Йорка (BS, 1917) Колумбийский университет (1918 г., доктор философии 1920 г.)
Известный	Формула 1 Проблема с перепиской Доказательство полноты Principia высказываний исчисления Формула обращения Поста Решетка поста Теорема Поста
Научная карьера
Поля	Математика , логика
Учреждения	Университет Принстон
Тезис	Введение в общую теорию элементарных предложений   (1920)
Докторантура	Кассиус Джексон Кейзер

Эмиль Леон Пост ( / poʊ st 11 февраля / ; 1897 — 21 апреля 1954) — американский математик и логик . Он наиболее известен своими работами в области, которая в конечном итоге стала известна как теория вычислимости .

Жизнь

Пост родился в Августове , Сувальская губерния , Конгресс Польши , Российская империя (ныне Польша) в польско-еврейской семье, иммигрировавшей в Нью-Йорк в мае 1904 года. Его родителями были Арнольд и Перл Пост.

Пост интересовался астрономией, но в возрасте двенадцати лет потерял левую руку в автокатастрофе. Эта потеря стала серьезным препятствием на пути к карьере профессионального астронома, что привело к его решению заняться математикой, а не астрономией.

Пост учился в средней школе Таунсенда Харриса и в 1917 году окончил Городской колледж Нью-Йорка со степенью бакалавра математики.

После получения докторской степени. Получив степень доктора математики в 1920 году в Колумбийском университете под руководством Кассиуса Джексона Кейзера , он получил докторскую степень в Принстонском университете в 1920–1921 учебном году. Затем Пост стал учителем математики в средней школе в Нью-Йорке.

Пост женился на Гертруде Сингер в 1929 году, от которой у него родилась дочь Филлис Пост Гудман (1932–1995). По совету своего врача Пост тратил на исследования не более трех часов в день, чтобы избежать маниакальных приступов, которые он испытывал еще с года обучения в Принстоне.

В 1936 году его назначили на математический факультет Городского колледжа Нью-Йорка. Он умер в 1954 году от сердечного приступа после лечения электрошоком от депрессии ; ему было 57.

Ранние работы

В своей докторской диссертации, позднее сокращенной и опубликованной как «Введение в общую теорию элементарных предложений» (1921), Пост доказал, среди прочего, что исчисление высказываний Principia Mathematica было полным: все тавтологии являются теоремами , учитывая Principia Mathematica аксиомы . а также правила замены и modus ponens . Пост также разработал таблицы истинности независимо от К.С. Пирса и Людвига Витгенштейна и нашел им хорошее математическое применение. Жана ван Хейеноорта В известном справочнике по математической логике (1966) перепечатана классическая статья Поста 1921 года, излагающая эти результаты.

Находясь в Принстоне, Пост был очень близок к открытию неполноты Principia Mathematica , которую Курт Гёдель доказал в 1931 году. Первоначально Пост не смог опубликовать свои идеи, поскольку считал, что для их принятия ему необходим «полный анализ». Как сказал Пост в открытке Гёделю в 1938 году:

Я бы открыл теорему Гёделя в 1921 году — если бы я был Гёделем.

Теория рекурсии

разработал В 1936 году Пост независимо от Алана Тьюринга математическую модель вычислений, которая по сути была эквивалентна модели машины Тьюринга . Задумав это как первую из серии моделей эквивалентной мощности, но возрастающей сложности, он назвал свою статью « Формула 1» . Эту модель иногда называют «машиной Поста» или машиной Пост-Тьюринга , но ее не следует путать с машинами тегов Поста или другими специальными видами канонической системы Поста , вычислительной моделью, использующей переписывание строк и разработанной Постом в 1920-х годах, но сначала опубликовано в 1943 году. Техника переписывания Поста в настоящее время повсеместно используется в спецификациях и проектировании языков программирования, и поэтому оказывает Чёрча лямбда-исчисление заметное влияние классической современной логики на практические вычисления. Пост разработал метод «вспомогательных символов», с помощью которого он мог канонически представлять любой постгенеративный язык, а также любую вычислимую функцию или множество вообще.

Системы соответствия были введены Постом в 1946 году, чтобы дать простые примеры неразрешимости . Он показал, что проблема соответствия Поста (PCP) удовлетворения их ограничений, вообще говоря, неразрешима. Неразрешимость проблемы соответствия оказалась именно тем, что было необходимо для получения результатов о неразрешимости в теории формальных языков .

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

Полиадические группы

Пост внес фундаментальный и до сих пор влиятельный вклад в теорию полиадических, или n -арных, групп в длинной статье, опубликованной в 1940 году. Его основная теорема показала, что полиадическая группа — это итеративное умножение элементов нормальной подгруппы группы . , такой, что факторгруппа является циклической порядка n - 1. Он также продемонстрировал, что полиадическая групповая операция на множестве может быть выражена через групповую операцию на том же множестве. В статье содержится много других важных результатов.

Избранные статьи

• Пост, Эмиль Леон (1919). «Обобщенные гамма-функции» . Анналы математики . Вторая серия. 20 (3): 202–217. дои : 10.2307/1967871 . JSTOR   1967871 .
• Пост, Эмиль Леон (1921). «Введение в общую теорию элементарных предложений». Американский журнал математики . 43 (3): 163–185. дои : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR   2370324 .
• Пост, Эмиль Леон (1936). «Конечные комбинаторные процессы - Формулировка 1». Журнал символической логики . 1 (3): 103–105. дои : 10.2307/2269031 . JSTOR   2269031 . S2CID   40284503 .
• Пост, Эмиль Леон (1940). «Полиадические группы» . Труды Американского математического общества . 48 (2): 208–350. дои : 10.2307/1990085 . JSTOR   1990085 .
• Пост, Эмиль Леон (1943). «Формальные редукции общей задачи комбинаторного решения». Американский журнал математики . 65 (2): 197–215. дои : 10.2307/2371809 . JSTOR   2371809 .
• Пост, Эмиль Леон (1944). «Рекурсивно перечислимые множества натуральных чисел и проблемы их решения» . Бюллетень Американского математического общества . 50 (5): 284–316. дои : 10.1090/s0002-9904-1944-08111-1 . Вводит важную концепцию сокращения «многие к одному» .

См. также

• Арифметическая иерархия
• Функциональная полнота
• Список нескольких открытий
• Список пионеров информатики

Ссылки

• Стиллвелл, Джон (2004), «Эмиль Пост и его ожидание Гёделя и Тьюринга» (PDF) , Mathematics Magazine , 77 (1): 3–14, doi : 10.2307/3219226 , JSTOR   3219226
• Уркхарт, Аласдер (2008). «Эмиль Пост» (PDF) . В Габбае, Дов М.; Вудс, Джон Вудс (ред.). Логика от Рассела к Чёрчу . Справочник по истории логики. Том. 5. Эльзевир Б.В.
• Нири, Терлоф (2015), «Неразрешимость в системах двоичных тегов и проблема почтового соответствия для пяти пар слов», Международный симпозиум по теоретическим аспектам информатики, Международные труды Лейбница по информатике (LIPIcs), страницы 649–661, 2015.

Дальнейшее чтение

• Аншель, Айрис Ли; Аншель, Майкл (ноябрь 1993 г.). «От постмарковской теоремы через проблемы принятия решений к криптографии с открытым ключом». Американский математический ежемесячник . 100 (9). Математическая ассоциация Америки: 835–844. дои : 10.2307/2324657 . JSTOR   2324657 .

  Посвящён Эмилю Посту и содержит специальные материалы о Посте. Сюда входит «Отношение Поста к криптологии и криптографистам его эпохи: ... Стивен Брэмс, известный теоретик игр и политолог, заметил нам, что жизнь и наследие Эмиля Поста представляют собой один аспект интеллектуальной жизни Нью-Йорка во время первой половины двадцатого века, которая очень нуждается в более глубоком исследовании. Авторы надеются, что эта статья послужит дальнейшему развитию этого исследования». (стр. 842–843)

• Дэвис, Мартин, изд. (1993). Неразрешимое . Дувр. стр. 288–406 . ISBN  0-486-43228-9 .

  Перепечатывает несколько статей Post.

• Дэвис, Мартин (1994). «Эмиль Л. Пост: его жизнь и творчество». Разрешимость, доказуемость, определимость: Собрание сочинений Эмиля Л. Поста . Биркхойзер. стр. xi – xxviii.

  Биографический очерк.

• Джексон, Аллин (май 2008 г.). «Интервью с Мартином Дэвисом» . Уведомления АМС . 55 (5): 560–571.

  Много материала об Эмиле Посте из его воспоминаний из первых рук.

• Джексон, Аллин (октябрь 2018 г.). «Эмиль Пост: Психологическая верность» . Заключение: Международное обозрение науки . дои : 10.37282/991819.18.48 . S2CID   240012225 .

  Биографическая статья.

Внешние ссылки

• Почтовые статьи Эмиля Леона 1927–1991 гг. , Американское философское общество , Филадельфия, Пенсильвания.
• «Празднование Эмиля Поста и его «неразрешимой проблемы» Тега: 100 лет спустя» . YouTube . Вольфрам. 19 мая 2021 г. Архивировано из оригинала 21 декабря 2021 г.