Emil Leon Post (; ) a fost un matematician și logician american. Este cel mai bine cunoscut pentru activitatea sa în domeniul care avea să fie cunoscut ca teoria calculabilității.

Viața Post s-a născut la Augustów, gubernia Suwałki, Polonia Congresului, Imperiul Rus (astăzi în Polonia) într-o familie de evrei din Polonia care a emigrat în New York City în mai 1904. Părinții lui erau Arnold și Pearl Post.

Post fusese interesat de astronomie, dar la vârsta de doisprezece ani și-a pierdut brațul stâng într-un accident de mașină. Această pierdere a constituit un obstacol important pentru posibila carieră de astronom, ceea ce l-a făcut să decidă să studieze matematica în schimb.

Post a învățat la și după absolvire a continuat studiile la pe care le-a terminat în 1917 cu o diplomă în matematică.

După doctoratul în matematică finalizat în 1920 la Universitatea Columbia, sub îndrumarea lui , a făcut un post-doctorat la Universitatea Princeton în anul universitar 1920–1921. Post a devenit apoi profesor de matematică la liceu în New York City.

Post s-a căsătorit cu Gertrude Singer (1900–1956) în 1929, cu care a avut o fiică, Phyllis Post Goodman (1932–1995). La sfatul medicului, Post și-a limitat timpul petrecut cu cercetarea la trei ore pe zi pentru a evita atacurile de manie, de care suferea din anul petrecut la Princeton.

În 1936, a fost numit în catedra de matematică de la City College of New York. A murit în aprilie 1954 de infarct miocardic suferit în urma unui pentru depresie.

Primele lucrări În teza de doctorat, care ulterior a fost publicată în variantă prescurtată sub titlul „Introducere într-o teorie generală a propozițiilor elementare” (1921), Post a demonstrat, printre altele, că din este complet: toate sunt teoreme, în baza axiomelor din și regulilor de și . Post a întocmit independent de C. S. Peirce și Ludwig Wittgenstein și le-a aplicat în matematică. Cartea de logică matematică din 1966 a lui a retipărit articolul clasic al lui Post din 1921 care enunța aceste rezultate.

La Princeton, Post s-a apropiat foarte mult de a descoperi incompletitudinea , pe care Kurt Gödel a demonstrat-o în 1931. Post nu și-a publicat la început ideile, întrucât credea că are nevoie de o „analiză completă” ca ele să fie acceptate. După cum îi spunea chiar lui Gödel într-o carte poștală din 1938:

Aș fi descoperit teorema lui Gödel în 1921—dacă eram Gödel.

Teoria recursiei În 1936, Post a dezvoltat, independent de Alan Turing, un model matematic de calcul care era în esență echivalent cu modelul mașinii Turing. El intenționa ca acesta să fie primul dintr-un șir de modele de putere echivalentă și complexitate crescândă, și și-a intitulat articolul . Acest model este adesea numit „mașina lui Post” sau , dar nu trebuie confundat cu sau cu alte feluri speciale de , un model computațional ce folosea , dezvoltat de Post în anii 1920 dar publicat în premieră în 1943. Tehnica de rescriere a lui Post este acum omniprezentă în specificațiile și designul limbajelor de programare, și astfel, împreună cu al lui Church, are o influență persistentă în logica clasică modernă și în tehnica practică de calcul. Post a gândit o metodă de „simboluri auxiliare” prin care reprezenta canonic orice limbaj Post-generativ, și, deci, orice funcție calculabilă sau .

Sistemele de corespondențe au fost introduse de Post în 1946 pentru a da exemple simple de . El a arătat că (PCP) de satisfacere a constrângerilor este, în general, indecidabilă. Indecidabilitatea problemei corespondenței s-a dovedit a fi exact lucrul de care era nevoie pentru a obține rezultate de indecidabilitate în teoria limbajelor formale.

Într-o influentă cuvântare ținută în fața Societății Americane de Matematică în 1944, el a ridicat chestiunea existenței unei necalculabile al cărui este mai mic decât cel al problemei opririi. Această problemă, care avea să rămână cunoscută drept problema lui Post, a stimulat multă activitate de cercetare. Ea a fost rezolvată cu răspuns afirmativ în anii 1950 prin introducerea puternicei metode a priorității în teoria calculabilității.

Grupuri poliadice Post a mai adus o contribuție fundamentală și încă influentă în teoria într-un lung articol publicat în 1940. Teorema lui principală arăta că un grup poliadic este produsul iterat al elementelor unui al unui grup, astfel încât grupul factor este de ordinul n − 1. El a demonstrat și că un o operație de grup poliadic pe o mulțime se poate exprima în termeni de operație de grup pe aceeași mulțime. Lucrarea conține și alte rezultate importante

Lucrări

Introduces importantul concept de .

Note

Bibliografie

Neary, Turlough (2015), "Undecidability in binary tag systems and the post correspondence problem for five pairs of words", International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs), paginile 649–661, 2015.

Categorie:Persoane cu tulburare bipolară Categorie:Logicieni americani Categorie:Amputați americani Categorie:Matematicieni americani din secolul al XX-lea Categorie:Decese în 1954 Categorie:Nașteri în 1897