Emil Leon Post

Emil Leon Post (ur. 11 lutego 1897 w Augustowie , zm. 21 kwietnia 1954 w Nowym Jorku ) – polski matematyk i logik .

Ż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ödla 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 .

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 . Jeśli możesz, .

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.

Bibliografia

• Davis, Martin (1993). The Undecidable (Ed.), ss. 288-406. Dover. . 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.

Zobacz też

• Problem odpowiedniości Posta

Linki zewnętrzne

• John J O'Connor; Edmund F. Robertson Emil Leon Post w MacTutor History of Mathematics archive ( ang. )

Przypisy