Емил Пост

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Емил Леон Пост
Emil Leon Post.jpg
американски математик от полски произход
Роден 11 февруари 1897
Аугустов, днес Полша
Починал 21 април 1954 г. (на 57 г.)
Ню Йорк Сити, САЩ

Емил Леон Пост е математик и логик. Той е най-добре познат с работата си по известната изчислителната теория.

Ранни години[редактиране | edit source]

Пост е роден в полско-еврейскo семейство баща Арнолд Пост и майка Перла Пост, което емигрира в САЩ, когато той е още дете. След като завършва докторантура по математика в Колумбийския университет, той става докторант в Принстънския университет. Докато е в Принстън, достига много близо до откриването на непълнотата на Principia Mathematica, което Курт Гьодел доказва през 1931 г. Пост след това става учител по математика в Ню Йорк Сити. През 1936 г. е назначен в катедра по математика в колеж на Ню Йорк, където остава до смъртта си през 1954 г.

Теория на рекурсията[редактиране | edit source]

През 1936 г. Пост развива, отделно от Алън Тюринг, математически модел на изчисление, което прилича на модела за машина на Тюринг. Възнамерявайки това да е първият от серия модели, еквивалентен по мощност, но с нарастваща сложност, той озаглавява своята статия Formulation 1. Този модел е понякога наричан "машина на Пост" или Машина на Пост-Тюринг, или други специални видове на каноничната система на Пост, разработена от Пост през 1920 година, но публикувана за първи път през 1943 година.

Пред Американското математическо общество през 1944 г. Пост повдига въпроса за съществуването на неизчислимо рекурсивно изброимо множество. Този въпрос, познат още като Проблем на Пост, е предпоставка за нови изследвания. През 1950-те години верността му е доказана с въвеждането на мощния метод на приоритизацията в теорията на рекурсията.

Избрани статии[редактиране | edit source]

  • 1936, "Finite Combinatory Processes - Formulation 1," Journal of Symbolic Logic 1: 103–105.
  • 1940, "Polyadic groups", Transactions of the American Mathematical Society 48: 208–350.
  • 1943, "Formal Reductions of the General Combinatorial Decision Problem," American Journal of Mathematics 65: 197–215.
  • 1944, "Recursively enumerable sets of positive integers and their decision problems," Bulletin of the American Mathematical Society 50: 284–316.

Източници[редактиране | edit source]

  • Emil Leon Post Papers 1927-1991 - American Philosophical Society, Philadelphia, Pennsylvania.
  • Davis, Martin (1993). The Undecidable (Ed.), pp. 288–406. Dover. ISBN 0-486-43228-9. Reprints several papers by Post.
  • Davis, Martin (1994). "Emil L. Post: His Life and Work" in Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhäuser: xi—xxviii. A biographical essay.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Emil Leon Post“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.