أطروحة تشرش-تورينغ
التاريخ > فترة 1930-1952

في سياق دراسة المشكلة، قدم تشرش وتلميذه ستيفن كلاين مفهوم الوظائف القابلة للتحديد، وتمكنا من إثبات أن العديد من الفئات الكبيرة من الوظائف التي يتم مواجهتها بشكل متكرر في نظرية الأعداد كانت قابلة للتحديد λ. بدأ النقاش عندما اقترحت تشيرش على جودل أن على المرء أن يعرف الوظائف «القابلة للحساب بشكل فعال» كوظائف قابلة للتحديد λ. ومع ذلك، لم يكن جودل مقتنعًا ووصف الاقتراح بأنه «غير مرض تمامًا». بدلاً من ذلك، في المراسلات مع تشيرش (حوالي 1934-1935)، اقترح جودل إضفاء البديهية على مفهوم «الحساب الفعال». في الواقع، في رسالة أرسلها تشرش عام 1935 إلى كلاين، أفاد تشرش بأن:
لكن جودل لم يقدم أي إرشادات أخرى. في النهاية، كان يقترح تكراره، بعد تعديله من خلال اقتراح هيربراند، الذي ذكره جودل بالتفصيل في محاضراته عام 1934 في برينستون نيوجيرسي (قام كلاين وروسر بنسخ الملاحظات). لكنه لم يعتقد أنه يمكن تحديد الفكرتين بشكل مرضٍ «إلا بطريقة الكشف عن مجريات الأمور».
بعد ذلك، كان من الضروري تحديد وإثبات تكافؤ مفهومين للقدرة على الحساب الفعال. مُجهزًا بحساب التفاضل والتكامل λ والعودة «العامة»، قدم ستيفن كلاين بمساعدة تشرش وجي باركلي روسر البراهين (1933، 1935) لإثبات أن الحسابين متكافئان. قام تشرش بعد ذلك بتعديل أساليبه لتشمل استخدام عودية هيربراند-جودل ثم أثبت (1936) أن مسألة القرار غير قابل للحل: لا توجد خوارزمية يمكنها تحديد ما إذا كانت الصيغة جيدة التكوين.
بعد عدة سنوات في رسالة إلى ديفيس (حوالي 1965)، قال جودل إنه «في وقت هذه المحاضرات [1934]، لم يكن مقتنعًا على الإطلاق بأن مفهومه للتكرار يشمل جميع عمليات التكرار الممكنة». بحلول عام 1963 - 1964، تنصل جودل من تكرار هيربراند-جودل وحساب التفاضل والتكامل لصالح آلة تورينج كتعريف لـ «الخوارزمية» أو «الإجراء الميكانيكي» أو «النظام الرسمي». فرضية تؤدي إلى قانون طبيعي؟: في أواخر عام 1936، تم تسليم ورقة آلان تورينج (التي تثبت أيضًا أن مشكلة مسألة القرار غير قابلة للحل) شفهيًا، ولكنها لم تظهر بعد في الطباعة. من ناحية أخرى، ظهرت ورقة Emil Post لعام 1936 وتم اعتمادها بشكل مستقل عن عمل تورينج. اختلف بوست بشدة مع «تحديد» تشيرش للحساب الفعال باستخدام حساب التفاضل والتكامل λ والتكرار. بدلاً من ذلك، اعتبر فكرة «القابلية للحساب الفعال» مجرد «فرضية عمل» قد تؤدي بالاستدلال الاستقرائي إلى «قانون طبيعي» بدلاً من «تعريف أو بديهية». انتقدت تشيرش هذه الفكرة «بشدة». وهكذا كان بوست في ورقته البحثية عام 1936 يستبعد أيضًا اقتراح كورت جودل للكنتش في 1934-1935 بأن الأطروحة يمكن التعبير عنها كبديهية أو مجموعة من البديهيات.
يضيف تورينج تعريفًا آخر، يساوي روسر الثلاثة: في غضون وقت قصير فقط، ظهرت ورقة تورينج 1936-1937 «حول الأرقام المحسوبة، مع تطبيق على مشكلة مسألة القرار». ذكر فيه فكرة أخرى عن «الحوسبة الفعالة» مع إدخال آلاته (المعروفة الآن باسم النموذج الحسابي المجرد لآلة تورينج). وفي رسم إثبات تمت إضافته باعتباره «ملحقًا» إلى ورقته البحثية 1936-1937، أظهر تورينج أن فئات الوظائف المحددة بواسطة حساب التفاضل والتكامل λ وآلات تورينج تتطابق. كان تشرش سريعًا في إدراك مدى جاذبية تحليل تورينج. في مراجعته لورقة تورينج أوضح أن فكرة تورينج جعلت «التماثل بفعالية في المعنى العادي (غير المحدد صراحة) واضحًا على الفور». في غضون بضع سنوات (1939) سيقترح تورينج، مثل تشرش وكلين من قبله، أن تعريفه الرسمي لعامل الحوسبة الميكانيكية هو التعريف الصحيح. وهكذا، بحلول عام 1939، اقترحت كل من تشيرش (1934) وتورنج (1939) بشكل فردي أن «الأنظمة الرسمية» يجب أن تكون تعريفات «للحساب الفعال».
أطروحة تشرش - تورينغ: ستيفن كلاين، في مقدمة عن الرياضيات، انتقل أخيرًا إلى تسمية «أطروحة تشيرش» و «أطروحة تورينج»، مستخدمًا نظريته في القابلية للتكرار. بعد أن تحول كلاين من تقديم عمله في مصطلحات تعريف تشيرش-كلين لامدا، إلى التكرار العودي جودل-كلين (الوظائف العودية الجزئية). في هذا الانتقال، عدل كلين وظائف جوديل العودية العامة للسماح بإثبات عدم قابلية حل المشكلات في حدس آي جي براور. في كتابه للخريجين حول المنطق، تم تقديم «أطروحة تشيرش» وتبيّن أن النتائج الرياضية الأساسية غير قابلة للتحقيق. بعد ذلك، يواصل كلاين تقديم «أطروحة تورينج»، حيث تظهر النتائج على أنها غير قابلة للحساب، مستخدمًا اشتقاقه المبسط لآلة تورينج بناءً على عمل إميل بوست. تم إثبات تكافؤ كلتا الأطروحتين باستخدام «نظرية XXX». أخيرًا، استخدم كلاين لأول مرة مصطلح «أطروحة تشيرش - تورينج» في قسم يساعد فيه على تقديم توضيحات للمفاهيم الواردة في ورقة ألان تورينج «مشكلة الكلمة في شبه المجموعات مع الإلغاء»، كما هو مطلوب في نقد من ويليام بون.