Emil Leon Post - Emil Leon Post
Emil Leon Post | |
---|---|
Urodzić się | 11 lutego 1897 |
Zmarł | 21 kwietnia 1954 Nowy Jork, USA
|
(w wieku 57)
Alma Mater |
City College of New York (BS, 1917) Columbia University (AM 1918, Ph.D. 1920) |
Znany z |
Preparat 1 post korespondencja problemem Kompletność-dowód Principia ' s rachunek zdań inwersja formuła Post krata Post twierdzenie Post |
Kariera naukowa | |
Pola | Matematyka , logika |
Instytucje | Uniwersytet Princeton |
Praca dyplomowa | Wprowadzenie do ogólnej teorii twierdzeń elementarnych (1920) |
Doradca doktorski | Cassius Jackson Keyser |
Emil Leon Post ( / p oʊ s t / ; 11 lutego 1897 – 21 kwietnia 1954) był urodzonym w Polsce amerykańskim matematykiem i logikiem . Najbardziej znany jest ze swojej pracy w dziedzinie, która ostatecznie stała się znana jako teoria obliczalności .
Życie
Post urodził się w Augustowie , Suwalszczyźnie , Kongresówce , Imperium Rosyjskim (obecnie Polska) w polsko-żydowskiej rodzinie, która wyemigrowała do Nowego Jorku w maju 1904 roku. Jego rodzicami byli Arnold i Pearl Post.
Post interesował się astronomią, ale w wieku dwunastu lat stracił lewą rękę w wypadku samochodowym. Ta strata była poważną przeszkodą w zostaniu zawodowym astronomem, co doprowadziło do jego decyzji o kontynuowaniu matematyki, a nie astronomii.
Post uczęszczał do Townsend Harris High School i kontynuował naukę w City College of New York w 1917 roku z tytułem licencjata z matematyki.
Po ukończeniu doktoratu z matematyki w 1920 r. na Columbia University pod kierunkiem Cassiusa Jacksona Keysera , w roku akademickim 1920–1921 odbył staż podoktorski na Uniwersytecie Princeton . Post następnie został nauczycielem matematyki w liceum w Nowym Jorku.
Post ożenił się z Gertrudą Singer w 1929 roku, z którą miał córkę Phyllis Post Goodman (1932-1995). Post spędzał najwyżej trzy godziny dziennie na badaniach za radą swojego lekarza, aby uniknąć ataków maniakalnych, których doświadczał od roku w Princeton.
W 1936 został powołany na wydział matematyki w City College of New York. Zmarł w 1954 roku o atak serca następującym leczenia elektrowstrząsami w depresji ; miał 57 lat.
Wczesna praca
W swojej pracy doktorskiej, później skróconej i opublikowanej jako „Wprowadzenie do ogólnej teorii propozycji elementarnych” (1921), Post udowodnił między innymi, że rachunek zdań Principia Mathematica jest kompletny: wszystkie tautologie są twierdzeniami , biorąc pod uwagę aksjomaty Principia oraz zasady substytucji i modus ponens . Post opracował również tabele prawdy niezależnie od Ludwiga Wittgensteina i CS Peirce'a i wykorzystał je do dobrego matematycznego wykorzystania. Dobrze znana książka źródłowa Jeana van Heijenoorta na temat logiki matematycznej (1966) przedrukowała klasyczny artykuł Posta z 1921 r. przedstawiający te wyniki.
Podczas pobytu w Princeton Post był bardzo bliski odkrycia niekompletności Principia Mathematica , co Kurt Gödel udowodnił w 1931 roku. Post początkowo nie opublikował swoich pomysłów, ponieważ uważał, że potrzebuje „pełnej analizy”, aby zostały zaakceptowane. Jak powiedział Post w pocztówce do Gödla w 1938 roku:
- Odkryłbym twierdzenie Gödla w 1921 roku — gdybym był Gödlem.
Teoria rekurencji
W 1936 Post opracował, niezależnie od Alana Turinga , matematyczny model obliczeń, który był zasadniczo równoważny modelowi maszyny Turinga . Zamierzając to jako pierwszy z serii modeli o równoważnej mocy, ale o rosnącej złożoności, zatytułował swój artykuł Formulation 1 . Model ten jest czasami nazywany „maszyną Posta” lub maszyną Post-Turinga , ale nie należy go mylić z maszynami tagów Posta lub innymi specjalnymi rodzajami systemu kanonicznego Posta , modelem obliczeniowym wykorzystującym przepisywanie ciągów i opracowanym przez Posta w latach dwudziestych XX wieku, ale najpierw opublikowana w 1943 roku. Technika przepisywania Posta jest obecnie wszechobecna w specyfikacji i projektowaniu języka programowania, tak więc w przypadku rachunku lambda Church'a wyraźny wpływ klasycznej nowoczesnej logiki na praktyczne obliczenia. Post opracował metodę „symboli pomocniczych”, dzięki której mógł kanonicznie reprezentować dowolny język postgeneratywny, a nawet każdą obliczalną funkcję lub zbiór w ogóle.
Systemy korespondencji zostały wprowadzone przez Post w 1946 r., aby podać proste przykłady nierozstrzygalności. Pokazał, że problem post-korespondencyjny (PCP) spełnienia ich ograniczeń jest w zasadzie nierozstrzygnięty. Nierozstrzygalność jego problemu z korespondencją pocztową okazała się dokładnie tym, co było potrzebne do uzyskania wyników nierozstrzygalności w teorii języków formalnych .
We wpływowym przemówieniu do Amerykańskiego Towarzystwa Matematycznego w 1944 r. podniósł kwestię istnienia nieobliczalnego, rekurencyjnie przeliczalnego zbioru, którego stopień Turinga jest mniejszy niż stopień zatrzymania . To pytanie, które stało się znane jako problem Posta , pobudziło wiele badań. Został on rozwiązany w sposób twierdzący w 1950 roku przez wprowadzenie potężnego sposobu pierwszeństwa w teorii rekursji .
Grupy poliadyczne
Post wniósł fundamentalny i wciąż wpływowy wkład w teorię grup poliadycznych, czyli n- arnych, w długim artykule opublikowanym w 1940 roku. Jego główne twierdzenie wykazało, że grupa poliadyczna jest iterowanym mnożeniem elementów normalnej podgrupy grupy , tak że grupa ilorazowa jest cykliczna rzędu n − 1. Wykazał również, że działanie grupy poliadycznej na zbiorze może być wyrażone jako działanie grupy na tym samym zbiorze. Artykuł zawiera wiele innych ważnych wyników.
Wybrane artykuły
- Poczta, Emil Leon (1919). „Uogólnione funkcje gamma” . Roczniki Matematyki . Druga seria. 20 (3): 202–217. doi : 10.2307/1967871 . JSTOR 1967871 .
- Poczta, Emil Leon (1921). „Wprowadzenie do ogólnej teorii propozycji elementarnych”. American Journal of Mathematics . 43 (3): 163–185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324 .
- Poczta, Emil Leon (1936). „Skończone procesy kombinacyjne – formuła 1”. Dziennik Logiki Symbolicznej . 1 (3): 103-105. doi : 10.2307/2269031 . JSTOR 2269031 .
- Post, Emil Leon (1940). „Grupy poliadyczne” . Transakcje Amerykańskiego Towarzystwa Matematycznego . 48 (2): 208–350. doi : 10.2307/1990085 . JSTOR 1990085 .
- Poczta, Emil Leon (1943). „Formalne redukcje ogólnego problemu kombinatorycznej decyzji”. American Journal of Mathematics . 65 (2): 197–215. doi : 10.2307/2371809 . JSTOR 2371809 .
- Post, Emil Leon (1944). „Rekurencyjnie przeliczalne zbiory liczb całkowitych dodatnich i ich problemy decyzyjne” . Biuletyn Amerykańskiego Towarzystwa Matematycznego . 50 (5): 284–316. doi : 10.1090/s0002-9904-1944-08111-1 .Wprowadza ważną koncepcję redukcji wielu-jednych .
Zobacz też
Uwagi
Bibliografia
- Stillwell, John (2004), "Emil Post i jego przewidywanie Gödla i Turinga" (PDF) , Matematyka Magazine , 77 (1): 3-14, doi : 10.2307/3219226 , JSTOR 3219226
- Urquhart, Alasdair (2008). "Emil Post" (PDF) . W Gabbay, Dov M.; Woods, John Woods (wyd.). Logika od Russella do Kościoła . Podręcznik Historii Logiki. 5 . Elsevier BV.
- Neary, Turlough (2015), „Nierozstrzygalność w binarnych systemach znaczników i problem korespondencji post dla pięciu par słów”, Międzynarodowe Sympozjum na temat Teoretycznych Aspektów Informatyki, Leibniz International Proceedings in Informatics (LIPICs), strony 649--661, 2015 .
Dalsza lektura
-
Anszel, Iris Lee; Anshel, Michael (listopad 1993). „Z twierdzenia Post-Markowa poprzez problemy decyzyjne do kryptografii klucza publicznego”. Amerykański miesięcznik matematyczny . Amerykańskie Stowarzyszenie Matematyczne. 100 (9): 835-844. doi : 10.2307/2324657 . JSTOR 2324657 .
- Dedykowane dla Emila Posta i zawiera specjalny materiał na Post. Obejmuje to „Związek Posta z kryptologią i kryptografią jego epoki: ... Steven Brams, znany teoretyk gier i politolog, zauważył, że życie i dziedzictwo Emila Posta reprezentuje jeden aspekt życia intelektualnego Nowego Jorku w okresie w pierwszej połowie XX wieku, która bardzo potrzebuje głębszych badań. Autorzy mają nadzieję, że niniejszy artykuł będzie służył dalszym dążeniom”. (s. 842–843)
-
Davis, Martin, wyd. (1993). Nierozstrzygnięty . Dover. str. 288 -406. Numer ISBN 0-486-43228-9.
- Przedruki kilku artykułów pocztą.
-
Davis, Martin (1994). „Emil L. Post: jego życie i praca”. Rozwiązywanie, sprawdzalność, definiowalność: Dzieła zebrane Emila L. Posta . Birkhäuser. s. xi–xxviii.
- Esej biograficzny.
-
Jackson, Allyn (maj 2008). „Wywiad z Martinem Davisem” . Zawiadomienia AMS . 55 (5): 560-571.
- Wiele materiałów na temat Emila Posta z jego wspomnień z pierwszej ręki.
Linki zewnętrzne
- Emil Leon Post Papers 1927-1991 , Amerykańskie Towarzystwo Filozoficzne , Filadelfia, Pensylwania.
- „Wspominamy Emila Posta i jego „nierozwiązywalny problem” Tag: 100 lat później” . YouTube . Wolfram. 19 maja 2021 r.