Емил Пост

Емил Леон Пост (на английски: Emil Leon Post) е американски математик и логик. Известен е най-вече с работата си по известната изчислителната теория.

Емил Леон Пост Emil Leon Post
американски математик
Роден	11 февруари 1897 г. Аугустов, днес Полша
Починал	21 април 1954 г. (57 г.) Ню Йорк Сити, САЩ
Погребан	САЩ
Учил в	Колумбийски университет[1]
Научна дейност
Област	Математика, информатика
Работил в	Принстънски университет (1920 – 1921) Колумбийски университет (1921 – 1924) Университет „Корнел“ (1924 – 1927)
Емил Леон Пост в Общомедия

Образование и ранна кариера

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

Теория на рекурсията

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

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

Избрани статии

• 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.

Източници

1. books.google.cat // с. 618.

• 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“ в: Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhäuser: xi—xxviii. Биографично есе.

Тази страница частично или изцяло представлява превод на страницата Emil Leon Post в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​