Emil Leon Post - Emil Leon Post
Emil Leon Post | |
|---|---|
 | |
| narozený | 11. února 1897 |
| Zemřel | 21.dubna 1954 (ve věku 57) New York City, USA |
| Alma mater | City College of New York (BS, 1917)[1] Columbia University (A.M.1918, Ph.D. 1920)[2] |
| Známý jako | Formulace 1 Problém s korespondencí Důkaz úplnosti Principia 's výrokový počet Vzorec inverze příspěvku Postova mříž Postova věta |
| Vědecká kariéra | |
| Pole | Matematika, logika |
| Instituce | Univerzita Princeton |
| Teze | Úvod do obecné teorie elementárních propozic (1920) |
| Doktorský poradce | Cassius Jackson Keyser |
Emil Leon Post (/poʊst/; 11. února 1897 - 21. dubna 1954) byl Američan polského původu matematik a logik. On je nejlépe známý pro jeho práci v oboru, který nakonec stal se známý jako teorie vypočítatelnosti.
Život
Post se narodil v Augustów, Guvernorát Suwałki, Kongres Polsko, Ruská říše (nyní Polsko) do a Polsko-židovský rodina, která se přistěhovala do New Yorku v květnu 1904. Jeho rodiči byli Arnold a Pearl Post.[2]
Post se zajímal o astronomii, ale ve dvanácti letech při automobilové nehodě přišel o levou ruku. Tato ztráta byla významnou překážkou profesionálního astronoma, což vedlo k jeho rozhodnutí věnovat se spíše matematice než astronomii.[3]
Post se zúčastnil Townsend Harris High School a pokračoval k absolvování City College of New York v roce 1917 s B.S. v matematice.[1]
Po dokončení jeho Ph.D. v matematice v roce 1920 v Columbia University, kontrolován Cassius Jackson Keyser, udělal post-doktorát na Univerzita Princeton v akademickém roce 1920–1921. Post se poté stal středoškolským učitelem matematiky v New Yorku.
Post se oženil s Gertrudou Singerovou v roce 1929, se kterou měl dceru Phyllis Goodman. Post strávil nanejvýš tři hodiny denně výzkumem na radu svého lékaře, aby se předešlo manickým útokům, které zažíval od svého roku v Princetonu.[4]
V roce 1936 byl jmenován do matematického oddělení na City College v New Yorku. Zemřel v roce 1954 na a infarkt Následující ošetření elektrošokem pro Deprese;[4][5] bylo mu 57.
Brzká práce
Ve své disertační práci, později zkrácené a publikované jako „Úvod do obecné teorie základních návrhů“ (1921), Post mimo jiné prokázal, že výrokový počet Principia Mathematica bylo kompletní: vše tautologie jsou věty, vzhledem k Principia axiomy a pravidla substituce a modus ponens. Příspěvek také vymyslel pravdivostní tabulky nezávisle na Ludwig Wittgenstein a C. S. Peirce a dobře je matematicky využít. Jean van Heijenoort Známá zdrojová kniha o matematické logice (1966) přetiskla Postův klasický článek z roku 1921, který uvádí tyto výsledky.
Zatímco v Princetonu, Post přišel velmi blízko k odhalení neúplnosti Principia Mathematica, který Kurt Gödel prokázáno v roce 1931. Post původně své myšlenky nezveřejnil, protože věřil, že pro jejich přijetí potřebuje „úplnou analýzu“.[2]
Teorie rekurze
V roce 1936 se Post vyvinul nezávisle na Alan Turing, matematický model výpočtu, který byl v podstatě ekvivalentní s Turingův model stroje. Zamýšlel to jako první ze série modelů ekvivalentní síly, ale se zvýšenou složitostí, nazval svůj příspěvek Formulace 1. Tento model se někdy nazývá „Postův stroj“ nebo a Post-Turingův stroj, ale nesmí být zaměňována s Příspěvkové značkovací stroje nebo jiné speciální druhy Postkanonický systém, výpočetní model využívající přepis řetězce a vyvinut Post ve 20. letech 20. století, ale poprvé publikován v roce 1943.[6] Technika přepsání Postu je nyní všudypřítomná ve specifikaci a designu programovacího jazyka, a tak s Churchovým lambda-kalkulem je výrazný vliv klasické moderní logiky na praktické výpočty. Post vymyslel metodu „pomocných symbolů“, pomocí kterých mohl kanonicky reprezentovat jakýkoli postgenerativní jazyk, a dokonce jakoukoli vypočítatelnou funkci nebo sadu vůbec.
Korespondenční systémy byly zavedeny poštou v roce 1946, aby poskytly jednoduché příklady nerozhodnutelnosti.[7] Ukázal, že Problém po korespondenci (PCP) uspokojení jejich omezení je obecně nerozhodnutelné. U 2 řetězcových párů se ukázalo, že PCP je rozhodnutelný v roce 1981. Je známo, že je nerozhodnutelný, když se použije 9 párů (nicméně Stephen Wolfram (2002) navrhli, že je nerozhodnutelný pouze s pouhými 3 páry).[8] Jeho nerozhodnutelnost Problém s korespondencí Ukázalo se, že to bylo přesně to, co bylo zapotřebí k získání výsledků nerozhodnutelnosti v teorii formální jazyky.
Ve vlivné adrese k Americká matematická společnost v roce 1944 nastolil otázku existence nepočitatelného rekurzivně vyčíslitelná množina jehož Turingův stupeň je menší než u zastavení problému. Tato otázka, která se stala známou jako Postův problém, stimuloval mnoho výzkumu. Bylo to vyřešeno kladně v padesátých letech zavedením mocných prioritní metoda v teorie rekurze.
Polyadické skupiny
Post zásadním a stále vlivným způsobem přispěl k teorii polyadic, nebo n-ary, groups v dlouhé práci publikované v roce 1940. Jeho hlavní teorém ukázal, že polyadická skupina je iterované násobení prvků normální podskupiny skupiny, takže kvocientová skupina je cyklická řádu n - 1. Rovněž prokázal, že operaci polyadické skupiny na množině lze vyjádřit pomocí operace skupiny na stejné sadě. Článek obsahuje mnoho dalších důležitých výsledků.
Vybrané příspěvky
- Post, Emil Leon (1921). „Úvod do obecné teorie elementárních návrhů“. American Journal of Mathematics. 43: 163–185. doi:10.2307/2370324. hdl:2027 / uiuo.ark: / 13960 / t9j450f7q.
- Post, Emil Leon (1936). "Konečné kombinované procesy - formulace 1". Journal of Symbolic Logic. 1: 103–105. doi:10.2307/2269031.
- Post, Emil Leon (1940). „Polyadic groups“. Transakce Americké matematické společnosti. 48: 208–350. doi:10.2307/1990085.
- Post, Emil Leon (1943). „Formální redukce problému obecného kombinatorického rozhodování“. American Journal of Mathematics. 65: 197–215. doi:10.2307/2371809.
- Post, Emil Leon (1944). "Rekurzivně vyčíslitelné množiny kladných celých čísel a jejich rozhodovací problémy". Bulletin of the American Mathematical Society. 50: 284–316. doi:10.1090 / s0002-9904-1944-08111-1. Představuje důležitý koncept mnoho-jedna redukce.
Viz také
Poznámky
- ^ A b Urquhart (2008)
- ^ A b C O'Connor, John J.; Robertson, Edmund F., "Emil Leon Post", MacTutor Historie archivu matematiky, University of St Andrews.
- ^ Urquhart (2008), s. 429.
- ^ A b Urquhart (2008), s. 430.
- ^ Baaz, Matthias, ed. (2011). Kurt Gödel a základy matematiky: Horizonty pravdy (1. vyd.). Cambridge University Press. ISBN 9781139498432.
- ^ Wolfram, Stephen (2002). Nový druh vědy. Wolfram Media, Inc. str.894, poznámka f. ISBN 1-57955-008-8.
- ^ E. L. Post (1946). "Varianta rekurzivně neřešitelného problému" (PDF). Býk. Amer. Matematika. Soc. 52: 264–269. doi:10.1090 / s0002-9904-1946-08555-9.
- ^ Wolfram, Stephen (2002). Nový druh vědy. Wolfram Media, Inc. str.1139. ISBN 1-57955-008-8.
Reference
- Stillwell, Johne (2004), „Emil Post a jeho očekávání Gödela a Turinga“ (PDF), Matematický časopis, 77 (1): 3–14, doi:10.2307/3219226, JSTOR 3219226
- Urquhart, Alasdair (2008). „Emil Post“ (PDF). In Gabbay, Dov M .; Woods, John Woods (eds.). Logika od Russella po církev. Příručka dějin logiky. 5. Elsevier BV.
Další čtení
- Anshel, Iris Lee; Anshel, Michael (listopad 1993). „Od postmarkovské věty přes problémy s rozhodováním až po kryptografii veřejného klíče“. Americký matematický měsíčník. Mathematical Association of America. 100 (9): 835–844. doi:10.2307/2324657. JSTOR 2324657.
- Věnováno Emilovi Postovi a obsahuje speciální materiál na Postu. To zahrnuje „Post's Relation to the Cryptology and Cryptographists of Era: ... Steven Brams, známý teoretik her a politolog, nám poznamenal, že život a odkaz Emila Posta představují jeden aspekt newyorského intelektuálního života během první polovina dvacátého století, která velmi potřebuje hlubší prozkoumání. Autoři doufají, že tento dokument slouží k dalšímu pronásledování “. (str. 842–843)
- Davis, Martin, ed. (1993). Nerozhodnutelný. Doveru. str.288 –406. ISBN 0-486-43228-9.
- Znovu vytiskne několik příspěvků poštou.
- Davis, Martin (1994). „Emil L. Post: Jeho život a dílo“. Řešitelnost, prokazatelnost, definovatelnost: Sebraná díla Emila L. Posta. Birkhäuser. str. xi – xxviii.
- Životopisná esej.
- Jackson, Allyn (květen 2008). „Rozhovor s Martinem Davisem“. Oznámení AMS. 55 (5): 560–571.
- Hodně materiálu o Emilovi Postovi z jeho vzpomínek z první ruky.
externí odkazy
- Emil Leon Post Papers 1927-1991, Americká filozofická společnost, Philadelphia, Pensylvánie.
