Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Эмиль Леон Пост ( / p s t / ; 11 февраля 1897 - 21 апреля 1954) был американским математиком и логиком польского происхождения . Он наиболее известен своей работой в области, которая в конечном итоге стала известна как теория вычислимости .

Жизнь [ править ]

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

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

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

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

Пост женился на Гертруде Сингер в 1929 году, от которой у него родилась дочь Филлис Гудман. Пост тратил не более трех часов в день на исследования по совету своего врача, чтобы избежать маниакальных приступов, которые он испытывал с года в Принстоне. [4]

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

Ранние работы [ править ]

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

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

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

Теория рекурсии [ править ]

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

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

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

Полиадические группы [ править ]

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

Избранные статьи [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ а б Уркхарт (2008)
  2. ^ a b c О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. , "Эмиль Леон Пост" , архив истории математики MacTutor , Университет Сент-Эндрюс.
  3. ^ Уркхарт (2008), стр. 429.
  4. ^ а б Уркхарт (2008), стр. 430.
  5. ^ Бааз, Матиас, изд. (2011). Курт Гёдель и основы математики: горизонты истины (1-е изд.). Издательство Кембриджского университета. ISBN 9781139498432.
  6. ^ Стиллвелл, Джон (2004). «Эмиль Пост и его ожидание Гёделя и Тьюринга» . Математический журнал . 77 (1): 3–14. DOI : 10.2307 / 3219226 . ISSN 0025-570X . 
  7. ^ Сообщение EL (1946). «Вариант рекурсивно неразрешимой задачи» (PDF) . Бык. Амер. Математика. Soc . 52 : 264–269. DOI : 10,1090 / s0002-9904-1946-08555-9 .

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

  • Аншель, Ирис Ли; Аншель, Майкл (ноябрь 1993 г.). «От теоремы Постмаркова через проблемы принятия решений к криптографии с открытым ключом». Американский математический ежемесячник . Математическая ассоциация Америки. 100 (9): 835–844. DOI : 10.2307 / 2324657 . JSTOR  2324657 .
    Посвящается Эмилю Посту и содержит специальные материалы о почте. Это включает в себя «Отношение Поста к криптологии и криптографистам его эпохи: ... Стивен Брамс, известный теоретик игр и политолог, заметил нам, что жизнь и наследие Эмиля Поста представляют собой один из аспектов интеллектуальной жизни Нью-Йорка во времена первая половина двадцатого века, которая очень нуждается в более глубоком исследовании. Авторы надеются, что эта статья послужит дальнейшему развитию этого исследования ». (стр. 842–843)
  • Дэвис, Мартин, изд. (1993). Неразрешимое . Дувр. стр.  288 -406. ISBN 0-486-43228-9.
    Перепечатывает несколько статей по почте.
  • Дэвис, Мартин (1994). «Эмиль Л. Пост: его жизнь и творчество». Разрешимость, доказуемость, определимость: Собрание сочинений Эмиля Л. Поста . Birkhäuser. стр. xi – xxviii.
    Биографический очерк.
  • Джексон, Аллин (май 2008 г.). «Интервью с Мартином Дэвисом» . Уведомления AMS . 55 (5): 560–571.
    Много материала об Эмиле Посте из его воспоминаний из первых рук.

Внешние ссылки [ править ]

  • Эмиль Леон Post Papers 1927–1991 , Американское философское общество , Филадельфия, Пенсильвания.