Emil Leon Post
Biografia
Emil Leon Post urodził się w Augustowie w rodzinie żydowskiej. Ojciec, Arnold J. Post, wyjechał do Stanów Zjednoczonych, a w maju 1904 roku do Ameryki przybyła żona Arnolda z synem Emilem i dwiema córkami. Zamieszkali w Harlemie. Emil Post jako dwunastolatek stracił lewą rękę.
Po obronie doktoratu z matematyki na Uniwersytecie Columbia w 1920 roku podjął studia podoktoranckie na Uniwersytecie w Princeton. Podczas pobytu w Princeton był 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, a od 1936 roku aż do śmierci w City College of New York.
W 1921 roku u niego objawiła się choroba maniakalno-depresyjna. Po drugim ataku choroby przestał nauczać na Cornell University i w latach dwudziestych XX wieku utrzymywał się, nauczając w George Washington High School w Nowym Jorku.
W 1929 roku ożenił się z Gertrudą Singer. Żona wspomagała go przy maszynopisaniu artykułów i listów oraz zajęła się stroną materialną życia. Ich jedyne dziecko to córka Phyllis Goodman.
W swojej pracy doktorskiej pisanej na Columbia University Post udowodnił, że rachunek zdań z Principia Mathematica jest zupełny, to znaczy że w systemie złożonym z aksjomatów podanych w Principia oraz reguł podstawiania i modus ponens wszystkie tautologie są twierdzeniami. Post wymyślił i wykorzystywał tablice prawdy. Najbardziej jest jednak znany ze swoich osiągnięć w teorii rekursji.
Cały czas zmagał się z maniakalno-depresyjną chorobą. W 1954 roku uległ nawrotom ataków. W kwietniu 1954 roku umarł na atak serca po leczeniu elektrowstrząsami w szpitalu dla umysłowo chorych w Nowym Jorku. Jego żona Gertrude Singer Post (ur. 1900) zmarła dwa lata później.
Od 1918 roku Post był członkiem American Mathematical Society, a od 1936 roku członkiem Association for Symbolic Logic.
Teoria rekursji
W 1936, niezależnie od Alana Turinga, zaproponował abstrakcyjny model obliczeń, nazwany „maszyną Posta”. Sformułował także tzw. problem odpowiedniości Posta oraz tzw. problem Posta (czy istnieje nieobliczalny, rekursyjnie przeliczalny zbiór o stopniu Turinga mniejszym niż stopień problemu stopu). Problem Posta znalazł pozytywne rozwiązanie w latach 50.
W 1936, „Finite Combinatory Processes – Formulation 1”, Journal of Symbolic Logic 1: s. 103–105. W 1943, „Formal Reductions of the General Combinatorial Decision Problem”, American Journal of Mathematics 65: s. 197–215. W 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.