Эмиль Леон Пост - Emil Leon Post

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

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

Жизнь

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

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

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

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

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

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

Ранняя работа

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

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

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

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

Системы соответствия были введены Постом в 1946 году, чтобы дать простые примеры неразрешимости.[7] Он показал, что Проблема с отправкой корреспонденции (PCP) выполнения их ограничений, как правило, неразрешимо. В 1981 году было показано, что с двумя парами строк, PCP разрешима. Известно, что он неразрешим, когда используются 9 пар (однако, Стивен Вольфрам (2002) предположили, что это также неразрешимо всего с 3 парами).[8] Неразрешимость его Проблема с почтовой корреспонденцией оказался именно тем, что нужно для получения неразрешимых результатов в теории формальные языки.

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

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

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

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

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

Смотрите также

Заметки

  1. ^ а б Уркхарт (2008)
  2. ^ а б c О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., "Эмиль Леон Пост", Архив истории математики MacTutor, Сент-Эндрюсский университет.
  3. ^ Уркхарт (2008), стр. 429.
  4. ^ а б Уркхарт (2008), стр. 430.
  5. ^ Бааз, Матиас, изд. (2011). Курт Гёдель и основы математики: горизонты истины (1-е изд.). Издательство Кембриджского университета. ISBN  9781139498432.
  6. ^ Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc. стр.894, примечание f. ISBN  1-57955-008-8.
  7. ^ Э. Л. Пост (1946). «Вариант рекурсивно неразрешимой проблемы» (PDF). Бык. Амер. Математика. Soc. 52: 264–269. Дои:10.1090 / с0002-9904-1946-08555-9.
  8. ^ Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc. стр.1139. ISBN  1-57955-008-8.

использованная литература

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

  • Аншель, Ирис Ли; Аншель, Майкл (ноябрь 1993 г.). «От теоремы Постмаркова через проблемы принятия решений к криптографии с открытым ключом». Американский математический ежемесячник. Математическая ассоциация Америки. 100 (9): 835–844. Дои: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.
    Много материала об Эмиле Посте из его воспоминаний из первых рук.

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