Emil Leon Post
Z Wikipedii
Emil Leon Post (ur. 11 lutego 1897 w Augustowie, zm. 21 kwietnia 1954 w Nowym Jorku), polski matematyk i logik.
Spis treści |
[edytuj] Życiorys
Post urodził się w polsko-żydowskiej rodzinie, która wyemigrowała do Stanów Zjednoczonych, gdy jeszcze był dzieckiem. Po obronie doktoratu z matematyki na Columbia University, poszedł na studia podoktoranckie na Princeton University. 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ödela w 1931 roku. Post pracował później w Nowym Jorku jako nauczyciel matematyki w szkole średniej. Od 1936 roku aż do śmierci pracował w City College of New York.
W swojej pracy doktorskiej pisanej na Columbia University Post udowodnił m.in., że rachunek zdań z Principia Mathemathica jest zupełny tj. ż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 Peirce'a Post wymyślił i wykorzystywał tabele prawdziwościowe [1]. Najbardziej jest jednak znany ze swoich osiągnięć w teorii rekursji.
[edytuj] Teoria rekursji
W roku 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.
Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.
[edytuj] Wybrane prace
- 1936, "Finite Combinatory Processes - Formulation 1," Journal of Symbolic Logic 1: ss. 103-105.
- 1943, "Formal Reductions of the General Combinatorial Decision Problem," American Journal of Mathematics 65: ss. 197-215.
- 1944, "Recursively enumerable sets of positive integers and their decision problems," Bulletin of the American Mathematical Society 50: ss. 284-316. Wprowadza ważne pojęcie redukcji many-one.
[edytuj] Bibliografia
- Davis, Martin (1993). The Undecidable (Ed.), ss. 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.
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- (en) John J O'Connor; Edmund F. Robertson Emil Leon Post w MacTutor History of Mathematics archive
- Emil Leon Post na stronie Mathematics Genealogy Project (jęz. angielski)
Przypisy
- ↑ 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
