Emil Leon Post

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Emil Leon Post
Emil Leon Post.jpg
Narození 11. února 1897
Augustov
Úmrtí 21. dubna 1954 (ve věku 57 let)
New York, USAUSA USA
Alma mater Kolumbijská univerzita
Zaměstnavatel City College of New York
Některá data mohou pocházet z datové položky.

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • Davis, Martin (1993). The Undecidable (Ed.), s. 288–406. Dover. ISBN 0-486-43228-9. 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.

Reference[editovat | editovat zdroj]

V tomto článku byly použity překlady textů z článků Emil Leon Post na slovenské Wikipedii a Emil Leon Post na polské Wikipedii.

Související články[editovat | editovat zdroj]