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.
Publikacje 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.
Przypisy
Bibliografia Davis, Martin (1993). The Undecidable (Ed.), s. 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.
Kategoria:Amerykańscy matematycy XX wieku Kategoria:Polscy logicy XX wieku Kategoria:Ludzie urodzeni w Augustowie Kategoria:Urodzeni w 1897 Kategoria:Zmarli w 1954