إميل ليون بوست

إميل ليون بوست ( 11 فبراير 1897 - 21 أبريل 1954) كان عالم رياضيات ومنطق أمريكي . اشتهر بعمله في المجال الذي أصبح فيما بعد يُعرف بنظرية الحوسبة .

وُلد بوست في أوغوستوف ، محافظة سووالكي ، بولندا الكونغرسية ، الإمبراطورية الروسية (بولندا الآن) لعائلة يهودية بولندية هاجرت إلى مدينة نيويورك في مايو 1904. كان والداه أرنولد وبيرل بوست. ^{[ 2 ]}

كان بوست مهتمًا بعلم الفلك، لكنه فقد ذراعه اليسرى في حادث سيارة وهو في الثانية عشرة من عمره. شكلت هذه الخسارة عائقًا كبيرًا أمام احترافه علم الفلك، مما دفعه إلى اتخاذ قرار بدراسة الرياضيات بدلًا من علم الفلك. ^{[ 3 ]}

التحق بوست بمدرسة تاونسند هاريس الثانوية ، ثم واصل دراسته ليحصل على شهادة البكالوريوس في الرياضيات من كلية مدينة نيويورك عام 1917. ^{[ 1 ]}

بعد حصوله على درجة الدكتوراه في الرياضيات عام 1920 من جامعة كولومبيا ، تحت إشراف كاسيوس جاكسون كايزر ، أجرى دراسات ما بعد الدكتوراه في جامعة برينستون خلال العام الدراسي 1920-1921. ثم عمل بوست مدرساً للرياضيات في إحدى مدارس مدينة نيويورك الثانوية.

تزوج بوست من جيرترود سينغر (1900-1956) عام 1929، وأنجب منها ابنةً تُدعى فيليس بوست غودمان (1932-1995). ^{[ 4 ]} كان بوست يقضي ثلاث ساعات كحد أقصى يوميًا في البحث بناءً على نصيحة طبيبه لتجنب نوبات الهوس التي كان يعاني منها منذ عامه الدراسي في جامعة برينستون. ^{[ 5 ]}

في عام 1936، عُيّن في قسم الرياضيات في كلية مدينة نيويورك. توفي في أبريل 1954 إثر نوبة قلبية بعد خضوعه للعلاج بالصدمات الكهربائية للاكتئاب . ^{[ 5 ] [ 6 ]}

في أطروحته للدكتوراه، التي اختُصرت لاحقًا ونُشرت بعنوان "مقدمة لنظرية عامة للقضايا الأولية" (1921)، أثبت بوست، من بين أمور أخرى، أن حساب القضايا في كتاب "الأصول الرياضية للفلسفة الطبيعية " (Principia Mathematica) كامل: فجميع التكرارات المنطقية هي نظريات ، بالنظر إلى بديهيات كتاب "الأصول الرياضية للفلسفة الطبيعية " وقواعد الاستبدال والقياس المنطقي . كما ابتكر بوست جداول الصواب بشكل مستقل عن تشارلز ساندرسون بيرس ولودفيج فيتجنشتاين ، ووظّفها استخدامًا رياضيًا جيدًا. وقد أعاد جان فان هيجينورت ، في كتابه المرجعي الشهير في المنطق الرياضي (1966)، نشر مقالة بوست الكلاسيكية لعام 1921 التي عرضت هذه النتائج.

أثناء دراسته في جامعة برينستون، كاد بوست أن يكتشف عدم اكتمال كتاب " برينسيبيا ماثيماتيكا" ، الذي أثبته كورت غودل عام 1931. في البداية، لم ينشر بوست أفكاره لاعتقاده أنه بحاجة إلى "تحليل كامل" ليتم قبولها. ^{[ 2 ]} وكما قال بوست في بطاقة بريدية إلى غودل عام 1938:

كنت سأكتشف نظرية غودل في عام 1921 لو كنت غودل. ^{[ 7 ]}

في عام 1936، طوّر بوست، بشكل مستقل عن آلان تورينج ، نموذجًا رياضيًا للحوسبة يُعادل نموذج آلة تورينج . وبهدف أن يكون هذا النموذج الأول في سلسلة من النماذج ذات القدرة المكافئة ولكن بتعقيد متزايد، عنون بحثه بـ" الصياغة 1" . يُطلق على هذا النموذج أحيانًا اسم "آلة بوست" أو " آلة بوست-تورينج "، ولكن لا ينبغي الخلط بينه وبين آلات الوسوم الخاصة ببوست أو أنواع أخرى خاصة من نظام بوست المتعارف عليه ، وهو نموذج حسابي يستخدم إعادة كتابة السلاسل النصية ، وقد طوّره بوست في عشرينيات القرن الماضي ونُشر لأول مرة عام 1943. أصبحت تقنية إعادة الكتابة الخاصة ببوست شائعة الاستخدام في مواصفات وتصميم لغات البرمجة، ولذا، إلى جانب حساب لامدا لتشرش ، يُعدّ هذا النموذج تأثيرًا بارزًا للمنطق الحديث الكلاسيكي على الحوسبة العملية. ابتكر بوست طريقة "الرموز المساعدة" التي مكّنته من تمثيل أي لغة توليدية خاصة ببوست تمثيلًا متعارفًا عليه، بل وأي دالة قابلة للحساب أو مجموعة قابلة للحساب على الإطلاق.

قدّم بوست أنظمة المراسلات عام 1946 لتقديم أمثلة بسيطة على عدم قابلية الحسم . ^{[ 8 ]} بيّن أن مسألة مراسلات بوست (PCP) المتمثلة في تلبية قيودها غير قابلة للحسم بشكل عام. وقد تبيّن أن عدم قابلية حسم مسألة المراسلات هو بالضبط ما كان مطلوبًا للحصول على نتائج عدم قابلية الحسم في نظرية اللغات الرسمية .

في خطاب مؤثر ألقاه أمام الجمعية الرياضية الأمريكية عام ١٩٤٤، طرح مسألة وجود مجموعة غير قابلة للحساب وقابلة للتعداد التكراري، بحيث تكون درجة تورينج الخاصة بها أقل من درجة تورينج الخاصة بمسألة التوقف . وقد حفزت هذه المسألة، التي عُرفت بمسألة بوست ، الكثير من الأبحاث. وتم حلها بالإيجاب في خمسينيات القرن العشرين من خلال إدخال طريقة الأولوية الفعالة في نظرية الحوسبة .

قدّم بوست إسهامًا جوهريًا ولا يزال مؤثرًا في نظرية الزمر متعددة الحدود، أو الزمر من الرتبة n ، في بحث مطوّل نُشر عام 1940. أظهرت نظريته الرئيسية أن الزمرة متعددة الحدود هي حاصل الضرب المتكرر لعناصر زمرة جزئية طبيعية من زمرة ، بحيث تكون زمرة القسمة دورية من الرتبة n − 1. كما برهن على إمكانية التعبير عن عملية زمرة متعددة الحدود على مجموعة بدلالة عملية زمرة على المجموعة نفسها. يحتوي البحث على العديد من النتائج المهمة الأخرى.

• بوست، إميل ل. (1919). "دوال غاما المعممة" . حوليات الرياضيات . السلسلة الثانية. 20 (3): 202-217 . doi : 10.2307/1967871 . JSTOR 1967871 . 
• بوست، إميل ل. (1921). "مقدمة لنظرية عامة للقضايا الأولية". المجلة الأمريكية للرياضيات . 43 (3): 163-185 . doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR 2370324 . 
• بوست، إميل ل. (1936). "العمليات التوافقية المحدودة - الصياغة 1". مجلة المنطق الرمزي . 1 (3): 103-105 . doi : 10.2307/2269031 . JSTOR 2269031. S2CID 40284503 .  
• بوست، إميل ل. (1940). "المجموعات متعددة الحدود" . معاملات الجمعية الرياضية الأمريكية . 48 (2): 208-350 . doi : 10.2307/1990085 . JSTOR 1990085 . 
• بوست، إميل ل. (1943). "الاختزالات الرسمية لمسألة القرار التوافقي العامة". المجلة الأمريكية للرياضيات . 65 (2): 197-215 . doi : 10.2307/2371809 . JSTOR 2371809 . 
• بوست، إميل ل. (1944). "مجموعات الأعداد الصحيحة الموجبة القابلة للتعداد بشكل متكرر ومسائل القرار الخاصة بها" . نشرة الجمعية الرياضية الأمريكية . 50 (5): 284-316 . doi : 10.1090/s0002-9904-1944-08111-1 .يقدم المفهوم المهم للاختزال المتعدد إلى واحد .

• التسلسل الهرمي الحسابي
• الاكتمال الوظيفي
• قائمة بالاكتشافات المتعددة
• قائمة رواد علوم الحاسوب

• ستيلويل، جون (2004)، "إميل بوست واستباقه لغودل وتورينج" (ملف PDF) ، مجلة الرياضيات ، 77 (1): 3-14 ، doi : 10.2307/3219226 ، JSTOR 3219226 
• أوركهارت، ألاسدير (2008). "إميل بوست" (ملف PDF) . في: غاباي، دوف م.؛ وودز، جون وودز (محرران). المنطق من راسل إلى تشيرش . دليل تاريخ المنطق. المجلد  5. إلسيفير بي في.
• Neary, Turlough (2015), "عدم قابلية الحسم في أنظمة العلامات الثنائية ومشكلة تطابق المنشور لخمسة أزواج من الكلمات"، الندوة الدولية حول الجوانب النظرية لعلوم الحاسوب، وقائع لايبنيز الدولية في المعلوماتية (LIPIcs)، الصفحات 649-661، 2015.

• أنشيل، إيريس لي؛ أنشيل، مايكل (نوفمبر 1993). "من نظرية ما بعد ماركوف مرورًا بمسائل القرار وصولًا إلى التشفير بالمفتاح العام". المجلة الرياضية الأمريكية الشهرية . 100 (9). الجمعية الرياضية الأمريكية: 835-844 . doi : 10.2307/2324657 . JSTOR 2324657 . 

  مُهدى إلى إميل بوست، ويحتوي على مواد خاصة عنه. يتضمن ذلك "علاقة بوست بعلم التشفير وعلماء التشفير في عصره: ... وقد أشار ستيفن برامز، عالم نظرية الألعاب وعالم السياسة البارز، إلى أن حياة إميل بوست وإرثه يُمثلان جانبًا من جوانب الحياة الفكرية في نيويورك خلال النصف الأول من القرن العشرين، وهو جانبٌ يستحقّ مزيدًا من البحث والتدقيق. ويأمل المؤلفون أن تُسهم هذه الورقة في تعزيز هذا المسعى". (ص  842-843)

• ديفيس، مارتن، محرر. (1993). غير القابل للحسم . دوفر. ص 288-406 . ISBN  0-486-43228-9.

  يعيد نشر العديد من المقالات التي كتبها بوست.

• ديفيس، مارتن (1994). "إميل ل. بوست: حياته وعمله". قابلية الحل، قابلية الإثبات، قابلية التعريف: الأعمال الكاملة لإميل ل. بوست . بيركهاوزر. الصفحات 11-28 . 

  مقال سيرة ذاتية.

• جاكسون، ألين (مايو 2008). "مقابلة مع مارتن ديفيس" . إشعارات الجمعية الأمريكية للرياضيات . 55 (5): 560-571 .

  الكثير من المواد المتعلقة بإميل بوست مستمدة من ذكرياته المباشرة.

• جاكسون، ألين (أكتوبر 2018). "إميل بوست: الإخلاص النفسي" . الاستدلال: مراجعة دولية للعلوم . doi : 10.37282/991819.18.48 . S2CID 240012225 . 

  مقال سيرة ذاتية.

• أوراق إميل ليون بوست 1927-1991 ، الجمعية الفلسفية الأمريكية ، فيلادلفيا، بنسلفانيا.
• "الاحتفال بإميل بوست و"مشكلته المستعصية" في لعبة المطاردة: بعد مرور 100 عام" . يوتيوب . وولفرام. 19 مايو 2021. مؤرشف من الأصل بتاريخ 21 ديسمبر 2021.