Emil Leon Post - Emil Leon Post

Emil Leon Post
Născut	11 februarie 1897 Augustów , Guvernoratul Suwałki , Congresul Polonia , Imperiul Rus (acum Polonia)
Decedat	21 aprilie 1954 (21.04.1954)(57 de ani) New York, SUA
Alma Mater	City College of New York (BS, 1917) Universitatea Columbia (AM 1918, dr. 1920)
Cunoscut pentru	Formularea 1 post problemă corespondență Integralitatea-dovada a Principia ' s propozitiilor calcul formula de inversare Post zăbrele Post teorema lui Post
Cariera științifică
Câmpuri	Matematică , logică
Instituții	Universitatea Princeton
Teză	Introducere într-o teorie generală a propunerilor elementare  (1920)
Consilier doctoral	Cassius Jackson Keyser

Emil Leon Post ( / p oʊ s t / ; 11 februarie 1897 - 21 aprilie 1954) a fost un matematician și logician american de origine poloneză . Este cunoscut mai ales pentru munca sa în domeniu, care în cele din urmă a devenit cunoscută sub numele de teoria calculabilității .

Viaţă

Post s-a născut în Augustów , guvernatul Suwałki , Congresul Polonia , Imperiul Rus (acum Polonia) într-o familie evreiască poloneză care a imigrat la New York în mai 1904. Părinții săi 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 reprezentat un obstacol semnificativ în calea de a fi un astronom profesionist, ducând la decizia sa de a urmări mai degrabă matematica decât astronomia.

Post a urmat liceul Townsend Harris și a continuat să absolvească City College din New York în 1917 cu un BS în matematică.

După finalizarea doctoratului. în matematică în 1920 la Columbia University , sub supravegherea lui Cassius Jackson Keyser , a făcut un post-doctorat la Universitatea Princeton în anul universitar 1920–1921. Post a devenit apoi profesor de matematică la New York.

Post s-a căsătorit cu Gertrude Singer în 1929, cu care a avut o fiică, Phyllis Post Goodman (1932-1995). Post a petrecut cel mult trei ore pe zi în cercetări la sfatul medicului său pentru a evita atacurile maniacale, pe care le trăise încă din anul său la Princeton.

În 1936, a fost numit la departamentul de matematică de la City College din New York. A murit în 1954, în urma unui atac de cord, în urma tratamentului cu electroșoc pentru depresie ; avea 57 de ani.

Munca timpurie

În teza sa de doctorat, scurtată ulterior și publicată ca „Introducere într-o teorie generală a propunerilor elementare” (1921), Post a demonstrat, printre altele, că calculul propozițional al Principia Mathematica a fost complet: toate tautologiile sunt teoreme , având în vedere axiomele Principiei. și regulile de substituție și modus ponens . Post a conceput, de asemenea, tabele de adevăr independent de Ludwig Wittgenstein și CS Peirce și le-a folosit la un bun folos matematic. Cunoscuta carte sursă despre logica matematică (1966) a lui Jean van Heijenoort a reeditat articolul clasic al lui Post din 1921, prezentând aceste rezultate.

În timp ce se afla la Princeton, Post a fost foarte aproape de a descoperi incompletitudinea Principiei Mathematica , pe care Kurt Gödel a dovedit-o în 1931. Post a eșuat inițial să-și publice ideile, deoarece credea că are nevoie de o „analiză completă” pentru ca acestea să fie acceptate. După cum a spus Post într-o carte poștală către Gödel în 1938:

Aș fi descoperit teorema lui Gödel în 1921 - dacă aș fi fost Gödel.

Teoria recursivității

În 1936, Post a dezvoltat, independent de Alan Turing , un model matematic de calcul care era în esență echivalent cu modelul mașinii Turing . Având intenția ca acesta să fie primul dintr-o serie de modele de putere echivalentă, dar cu o complexitate crescândă, el și-a intitulat lucrarea Formulare 1 . Acest model este uneori numit „mașina lui Post” sau o mașină Post-Turing , dar nu trebuie confundat cu mașinile de etichetare ale Post sau cu alte tipuri speciale de sistem canonic Post , un model de calcul care folosește rescrierea șirurilor și dezvoltat de Post în anii 1920, dar mai întâi publicat în 1943. Tehnica de rescriere a lui Post este acum omniprezentă în specificațiile și proiectarea limbajului de programare, așa că, cu calculul lambda al Church, este o influență evidentă a logicii moderne clasice asupra calculului practic. Post a conceput o metodă de „simboluri auxiliare” prin care ar putea reprezenta în mod canonic orice limbaj post-generativ și, într-adevăr, orice funcție sau set calculabil.

Sistemele de corespondență au fost introduse de Post în 1946 pentru a da exemple simple de indecidabilitate. El a arătat că problema postcorespondență (PCP) a satisfacerii constrângerilor lor este, în general, indecidabilă. Undecidabilitatea problemei sale de corespondență Post s -a dovedit a fi exact ceea ce era necesar pentru a obține rezultate de indecidabilitate în teoria limbajelor formale .

Într-o adresare influentă adresată Societății Americane de Matematică din 1944, el a ridicat problema existenței unui set necomputabil recursiv enumerabil al cărui grad de Turing este mai mic decât cel al problemei de oprire . Această întrebare, care a devenit cunoscută sub numele de problema lui Post , a stimulat multe cercetări. Acesta a fost rezolvat afirmativ în anii 1950 prin introducerea metodei prioritare puternice în teoria recursivității .

Grupuri poliadice

Post a adus o contribuție fundamentală și încă influentă la teoria grupurilor poliadice sau n -ary într-o lucrare lungă publicată în 1940. Teorema sa majoră a arătat că un grup poliadic este multiplicarea iterată a elementelor unui subgrup normal al unui grup , astfel încât grupul coeficientului este ciclic de ordinul n - 1. El a demonstrat, de asemenea, că o operație de grup poliadic pe un set poate fi exprimată în termeni de operație de grup pe același set. Lucrarea conține multe alte rezultate importante.

Lucrări selectate

• Post, Emil Leon (1919). „Funcțiile Gamma Generalizate” . Analele matematicii . A doua serie. 20 (3): 202–217. doi : 10.2307 / 1967871 . JSTOR  1967871 .
• Post, Emil Leon (1921). „Introducere într-o teorie generală a propunerilor elementare”. American Journal of Mathematics . 43 (3): 163–185. doi : 10.2307 / 2370324 . hdl : 2027 / uiuo.ark: / 13960 / t9j450f7q . JSTOR  2370324 .
• Post, Emil Leon (1936). "Procese combinatorii finite - formularea 1". Jurnal de logică simbolică . 1 (3): 103–105. doi : 10.2307 / 2269031 . JSTOR  2269031 .
• Post, Emil Leon (1940). „Grupuri poliadice” . Tranzacțiile Societății Americane de Matematică . 48 (2): 208-350. doi : 10.2307 / 1990085 . JSTOR  1990085 .
• Post, Emil Leon (1943). „Reduceri formale ale problemei deciziei combinatorii generale”. American Journal of Mathematics . 65 (2): 197-215. doi : 10.2307 / 2371809 . JSTOR  2371809 .
• Post, Emil Leon (1944). „Seturi recursiv de numere întregi pozitive și problemele lor de decizie” . Buletinul Societății Americane de Matematică . 50 (5): 284-316. doi : 10.1090 / s0002-9904-1944-08111-1 .Prezintă conceptul important de reducere multi-unu .

Vezi si

• Ierarhia aritmetică
• Completitudine funcțională
• Lista multiplelor descoperiri
• Lista pionierilor în informatică

Note

Referințe

• Stillwell, John (2004), „Emil Post and His Anticipation of Gödel and Turing” (PDF) , Mathematics Magazine , 77 (1): 3-14, doi : 10.2307 / 3219226 , JSTOR  3219226
• Urquhart, Alasdair (2008). „Emil Post” (PDF) . În Gabbay, Dov M .; Woods, John Woods (eds.). Logică de la Russell la Biserică . Manual de istorie a logicii. 5 . Elsevier BV.
• 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 .

Lecturi suplimentare

• Anshel, Iris Lee; Anshel, Michael (noiembrie 1993). „De la teorema post-Markov prin probleme de decizie la criptografie cu cheie publică”. The American Mathematical Monthly . Asociația Matematică a Americii. 100 (9): 835-844. doi : 10.2307 / 2324657 . JSTOR  2324657 .

  Dedicat Emil Post și conține materiale speciale pe Post. Aceasta include „Relația lui Post cu criptologia și criptografiștii epocii sale: ... Steven Brams, cunoscutul teoretician al jocului și politolog, ne-a remarcat că viața și moștenirea lui Emil Post reprezintă un aspect al vieții intelectuale din New York în timpul prima jumătate a secolului al XX-lea, care are foarte mult nevoie de o explorare mai profundă. Autorii speră că această lucrare va servi la continuarea acestei căutări ". (pp. 842-843)

• Davis, Martin, ed. (1993). Indecidabilul . Dover. pp.  288 –406. ISBN 0-486-43228-9.

  Reimprimă mai multe lucrări prin poștă.

• Davis, Martin (1994). „Emil L. Post: Viața și opera sa”. Solubilitate, disponibilitate, definibilitate: lucrările colectate ale lui Emil L. Post . Birkhäuser. pp. xi – xxviii.

  Un eseu biografic.

• Jackson, Allyn (mai 2008). „Un interviu cu Martin Davis” . Notificări ale AMS . 55 (5): 560-571.

  Mult material despre Emil Post din amintirile sale din prima mână.

linkuri externe

• Emil Leon Post Papers 1927-1991 , American Philosophical Society , Philadelphia, Pennsylvania.
• „Sărbătorirea lui Emil Post și„ Problema sa inaccesibilă ”a etichetei: 100 de ani mai târziu” . YouTube . Wolfram. 19 mai 2021.