Emil Leon Post
Emil Leon Post (11. února 1897 Augustów, Ruské impérium (v současnosti Polsko) – 21. dubna 1954 New York, USA) byl polsko-americký matematik a logik židovského původu. Je známý zejména díky svému přínosu v matematické logice, teorii vyčíslitelnosti a teorii formálních jazyků.

Biografie 
Post se narodil v polské ortodoxní židovské rodině. Otec v roce 1897 emigroval do USA a když se mu začalo dařit, přijela za ním i jeho rodina – sedmiletý Emil, jeho dvě sestry a matka. Rodina bydlela v komfortním bytě v Haarlemu. Jako dítě byl Emil uchvácen astronomií, ale jeho plány zhatilo neštěstí, když ve dvanácti letech přišel o levou ruku. Před ukončením školní docházky podal dotaz v několika observatořích, zda jeho postižení není na překážku dráze astronoma. Obdržené odpovědi ho od dětských ambicí odradily a Emil se začal věnovat matematice.

Po obhájení doktorátu z matematiky na Kolumbijské univerzitě v roce 1921 nastoupil na postdoktorské studium na univerzitě v Princetonu. Po dobu pobytu v Princetonu byl velmi blízko objevu, że systém představený v Principia mathematica Bertranda Russella a Alfreda North Whiteheada je neúplný, což bylo zdůvodněno teprve Kurtem Gödelem v roce 1931 (Gödelovy věty o neúplnosti). Post pracoval později v New Yorku jako učitel matematiky na střední škole. Od roku 1936 až do své smrti pracoval v City College of New York.

Teorie rekurze 
V roce 1936 uvedl předpoklad abstraktního modelu výpočtu, nazvaný „Postův stroj”, a to nezávisle na Alanu Turingovi, tvůrci ekvivalentního Turingova stroje (nazývaného také Postův-Turingův stroj).

Zformuloval a roku 1946 představil Postův korespondenční problém, jehož nerozhodnutelnost hraje mimořádně důležitou roli při dokazování nerozhodnutelnosti mnoha jiných problémů; rozvinut byl v 50. letech.

Vybraná díla 
 1936, „Finite Combinatory Processes – Formulation 1”, Journal of Symbolic Logic 1: s. 103-105.
 1943, „Formal Reductions of the General Combinatorial Decision Problem”, American Journal of Mathematics 65: s. 197-215.
 1944, „Recursively enumerable sets of positive integers and their decision problems”, Bulletin of the American Mathematical Society 50: s. 284-316.

Bibliografie 
 Davis, Martin (1993). The Undecidable (Ed.), s. 288–406. Dover. . Obsahuje přetisky některých Postových prací.
 Davis, Martin (1994). „Emil L. Post: His Life and Work” w: Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhäuser: xi—xxviii. Biografická esej.

Odkazy

Reference

Související články 
 Postova věta
 Postův korespondenční problém

Externí odkazy 
 

Muži
Polští matematici
Američtí matematici
Američtí logici
Polští logici
Židovští matematici
Polští Židé
Američtí Židé
Narození v roce 1897
Narození 11. února
Úmrtí v roce 1954
Úmrtí 21. dubna
Úmrtí v New Yorku
Absolventi Kolumbijské univerzity