Emil Post

Emil Leon Post Biografie

Naștere	11 februarie 1897 Augustów ( Imperiul Rus )
Moarte	21 aprilie 1954(în vârstă de 57 de ani) New York
Înmormântare	Cimitirul Muntele Hebron ( în )
Numele în limba maternă	Emil Leon Post
Numele nașterii	Emil Leon Post
Naţionalitate	american
Instruire	Liceul Townsend Harris ( în ) (până la1913) Universitatea Columbia (1917-1920) City College din New York (până la1917)
Activități	Matematician , filosof , logician , profesor universitar

Alte informații

Lucrat pentru	Universitatea Princeton (1920-1921) , Universitatea Columbia (1921-1924) , Universitatea Cornell (1924-1927) , George Washington High School ( ro ) (1927-1932) , City College din New York (1932-1954)
Camp	Matematică
Supervizor	Cassius Jackson Keyser (1920)
Arhive păstrate de	Biblioteca Societății Filozofice Americane ( d ) (Mss.Ms.Coll.45)

Lucrări primare

Problema post corespondenta , Post inversiune formula ( d ) , zăbrele Post ( d ) , teorema post , sistem canonic post

Emil Leon Post (născut pe11 februarie 1897în Augustów și a murit pe21 aprilie 1954în New York) este un matematician american născut pe teritoriul Poloniei actuale într-o familie de evrei . El este sursa problemei de corespondență a lui Post .

De asemenea, a publicat în 1921 un studiu exhaustiv al clonelor algebrelor cu doi elemente.

Biografie

Emil Post s-a născut în Polonia în 1897 sub numele Postawelski, a emigrat împreună cu familia sa în Statele Unite în 1904 unde i s-a americanizat numele.

Avea brațul stâng amputat la vârsta de 13 ani în urma unui accident de mașină. El nu va evoca acest eveniment de-a lungul vieții și pozează întotdeauna într-o fotografie, astfel încât să nu vedem brațul lipsă.

Un student strălucit, a obținut o teză la Universitatea Columbia în 1920, apoi și-a început cercetările în logică anul următor la Princeton datorită unei burse.

A suferit o criză în 1921, apoi o a doua în 1924, care l-a îndepărtat de munca sa de logică până în 1936, când a revenit la muncă în timp limitat.

El a murit pe 21 aprilie 1954 în urma tratamentului cu electroșoc, fiind internat din vara anterioară.

Lucrați la calculul propozițional

În Introducerea sa la o teorie generală a propozițiilor elementare din 1921, el stabilește completitudinea semantică a calculului propozițional al Principia Mathematica a lui Whitehead și Russell prin sistemul tabelelor de adevăr . Apoi el generalizează acest rezultat la orice calcul propozițional finit-valent (și nu doar bivalent ).

Problema corespondenței postului

Începem de la două secvențe finite U și V care conțin același număr de cuvinte finite pe orice alfabet. de exemplu

u_ {1} = aba, u_ {2} = b, u_ {3} = a, u_ {4} = ab \ qquad {\ textrm {et}} \ qquad v_ {1} = a, v_ {2} = b, v_ {3} = ababa, v_ {4} = b ~

Căutăm o secvență de indici astfel încât concatenarea lui să corespundă cu cea a . Aici secvența (1,2,3,2,1) este o soluție deoarece $i_ {1}, i_ {2}, ... i_ {n}$ $u _ {{i_ {k}}}$ $v _ {{i_ {k}}}$

u_ {1} u_ {2} u_ {3} u_ {2} u_ {1} = v_ {1} v_ {2} v_ {3} v_ {2} v_ {1} = ababababa ~

Problema de potrivire a postării (abreviată cu PCP) este de a determina dacă există o astfel de secvență. Este indecidabil : nu există un algoritm general capabil să ofere un răspuns pentru U și V. arbitrare.

Bibliografie

Înregistrări de autoritate :
(en) Emil Post, Introducere într-o teorie generală a propozițiilor elementare , 1921. Reprodus în (en) Jean van Heijenoort ( ed. ), De la Frege la Gödel : A Source Book in Mathematical Logic, 1879-1931 , Harvard Univ. Presa.,1977( 1 st ed. 1967) ( prezentare online )pp. 264-283. Traducere franceză, Jean Largeault ( ed. ), Logică matematică: texte , Armand Colin,1972
(ro) Emil L. Post , Solvability, Provability, Definability: the Complete Works of Emil L. Post , Boston, Basel, Birkhaüser ,1994

Evaluare și referință

(în) EL Post, „ O variantă a unei probleme insolvabile recursiv ” , Bull. Amar. Matematica. Soc , vol. 52, 1946( citește online )
Pierre Cassou-Noguès, Demonii lui Gödel, Logică și nebunie , Prag,2007, 411 p. , Partea a IV-a: The Post Case, o scurtă divagare. Pagini 253-257