Emil Leon Post

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Emil Leon Post

Emil Leon Post (ur. 11 lutego 1897 w Augustowie, zm. 21 kwietnia 1954 w Nowym Jorku) – amerykański matematyk i logik polskiego pochodzenia.

Życiorys[edytuj | edytuj kod]

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 tautologietwierdzeniami. 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[edytuj | edytuj kod]

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.

Wiki letter w.svg Ta sekcja jest niekompletna. Jeśli możesz, rozbuduj ją.

Wybrane prace[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

  • 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.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Przypisy

  1. 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