Emil Leon Post
Emil Leon Post (ur. 11 lutego 1897 w Augustowie, zm. 21 kwietnia 1954 w Nowym Jorku) – pochodzący z terenów dzisiejszej Polski amerykański matematyk i logik pochodzenia żydowskiego.
Życiorys
Post urodził się w żydowskiej rodzinie[1], która wyemigrowała do Stanów Zjednoczonych, gdy jeszcze był dzieckiem. Po obronie doktoratu z matematyki na Uniwersytecie Columbia, poszedł na studia podoktoranckie na Uniwersytecie w Princeton. Podczas pobytu w Princeton był bardzo bliski odkrycia, że system przedstawiony w Principia mathematica Russella i Whiteheada jest niezupełny, co zostało udowodnione dopiero przez Kurta Gödla w 1931. Post pracował później w Nowym Jorku jako nauczyciel matematyki w szkole średniej. Od 1936 aż do śmierci pracował w City College of New York.
W swojej pracy doktorskiej pisanej na Columbia University Post udowodnił, że rachunek zdań z Principia mathemathica jest zupełny, to znaczy że w systemie złożonym z aksjomatów podanych w Principiach oraz reguł podstawiania i modus ponens wszystkie tautologie są twierdzeniami. Niezależnie od Wittgensteina i Charlesa Sandersa Peirce’a Post wymyślił i wykorzystywał tablice prawdy[2]. Najbardziej jest jednak znany ze swoich osiągnięć w teorii rekursji.
Teoria rekursji
W 1936, niezależnie od Alana Turinga (twórcy maszyny Turinga), zaproponował abstrakcyjny model obliczeń, nazwany „maszyną Posta”.
Sformułował tzw. problem odpowiedniości Posta oraz tzw. problem Posta (czy istnieje nieobliczalny, rekurencyjnie przeliczalny zbiór o stopniu Turinga mniejszym niż stopień problemu stopu). Problem Posta znalazł pozytywne rozwiązanie w latach 50.
Wybrane prace
- 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. Wprowadza ważne pojęcie redukcji many-one.
Bibliografia
- Davis, Martin (1993). The Undecidable (Ed.), s. 288–406. Dover. ISBN 0-486-43228-9. Zawiera przedruki niektórych prac Posta.
- 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. Esej biograficzny.
Linki zewnętrzne
John J. O'Connor; Edmund F. Robertson: Emil Leon Post w MacTutor History of Mathematics archive (ang.)
Przypisy
- ↑ J.J. O'Connor, E.F. Robertson: Emil Leon Post, wrzesień 2001
- ↑ Odpowiedni tekst Posta znajduje się w książce From Frege To Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard Uni. Press, 1967