אמיל ליאון פוסט (Emil Leon Post) הגיע למסקנה בנוגע לשלמות של תחשיב הפסוקים בשנת 1921, ומיפה ביעילות את יסודות הלוגיקה של הפרינקיפיה מתמטיקה (Principia Mathematica). הקריירה שלו התפתחה באמצעות מחקר מתמטי משמעותי בארצות הברית, החל מלימודי הדוקטורט המוקדמים שלו באוניברסיטת קולומביה (Columbia University) ועד לתפקידו ארוך השנים בהוראה בסיטי קולג' של ניו יורק (City College of New York).
יסודות אקדמיים
פוסט נולד באוגוסטוב בשנת 1897 ועבר לעיר ניו יורק בילדותו. הוא למד בתיכון טאונסנד האריס (Townsend Harris High School) והשלים תואר ראשון בסיטי קולג' של ניו יורק לפני שקיבל דוקטורט מאוניברסיטת קולומביה בשנת 1920 בהנחייתו של קסיוס ג'קסון קייזר (Cassius Jackson Keyser). מסלולו המקצועי המוקדם כלל שנת פוסט-דוקטורט באוניברסיטת פרינסטון (Princeton University), שלאחריה תקופות באוניברסיטת קורנל (Cornell University) והוראה בבתי ספר תיכוניים, עד שקיבל מינוי סגל בסיטי קולג' של ניו יורק בשנת 1932.
לוגיקה וחישוביות
פוסט פיתח באופן עצמאי טבלאות אמת והרחיב את תורת הפסוקים האלמנטריים. עד שנת 1936, הוא ניסח מודל חישוב השקול למכונת טיורינג, המכונה כיום מכונת פוסט-טיורינג. עבודתו על מערכות קנוניות, שפורסמה בשנת 1943, ביססה שיטות לכתיבה מחדש של מחרוזות שנותרו בסיסיות לתכנון שפות תכנות מודרניות. בשנת 1946, הוא הציג את בעיית ההתאמה של פוסט כדי להדגים אי-כריעות בשפות פורמליות.
חבורות פוליאדיות ובעיית פוסט
מעבר לתרומותיו לחישוביות, פוסט ערך מחקר מקיף בחבורות פוליאדיות, או n-אריות. המאמר שלו משנת 1940 סיפק משפט יסודי שהוכיח כי ניתן לבטא מבנים כאלה באמצעות פעולות חבורה סטנדרטיות. מאוחר יותר, בנאום בפני האגודה האמריקאית למתמטיקה (American Mathematical Society) בשנת 1944, הוא הציע שאלה בנוגע לקיומה של קבוצה רקורסיבית מנייה שאינה ניתנת לחישוב עם דרגת טיורינג נמוכה מבעיית העצירה, אתגר הידוע כיום כבעיית פוסט.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →ניהול הבריאות
החל מתקופתו בפרינסטון, פוסט נאבק בהתקפי מאניה. בעקבות ייעוץ רפואי, הוא הגביל את משך המחקר היומי שלו ללא יותר משלוש שעות. הוא נישא לגרטרוד זינגר (Gertrude Singer) בשנת 1929, ונולדה להם בת, פיליס פוסט גודמן (Phyllis Post Goodman). פוסט מת מהתקף לב בעיר ניו יורק בשנת 1954 לאחר שעבר טיפול בנזעי חשמל לדיכאון ונקבר בבית העלמין מאונט חברון (Mount Hebron Cemetery).
עובדות מהירות
- נולד: 1897, אוגוסטוב - נפטר: 1954, ניו יורק - השכלה: סיטי קולג' של ניו יורק, אוניברסיטת קולומביה - בת זוג: גרטרוד זינגר - בת: פיליס פוסט גודמן - תרומה מרכזית: בעיית ההתאמה של פוסט - מקום מנוחה אחרון: בית העלמין מאונט חברון
שאלות נפוצות של קוראים
### מה הייתה החשיבות של התזה משנת 1921?
היא הוכיחה שתחשיב הפסוקים של הפרינקיפיה מתמטיקה הוא שלם, כלומר שכל הטאוטולוגיות הן תאורמות.
### האם פוסט גילה את משפטי האי-שלמות של גדל קודם לכן?
פוסט היה קרוב לתגלית בעת שהותו בפרינסטון בשנת 1921 אך לא פרסם את רעיונותיו באותה עת.