أطروحة تشرش-تورينغ
في نظرية القابلية للحساب، تعرف أطروحة تشرش-تورنغ Church-Turing Thesis، أو حدسية تشرش-تورنغ Church-Turing Conjecture، على أنها فرضية Hypothesis حول طبيعة الدوال الحسابية Computable functions. تنص الفرضية على أن الأعداد الطبيعية تكون قابلة للحساب بعقل إنساني وبخوارزمية، مع تجاهل القيود على الموارد، إذا وفقط كانت محسوبة باستخدام آلة تورنغ. الأطروحة سميت على عالم الرياضيات الأمريكي ألونزو تشرش وعالم الرياضيات البريطاني آلان تورنغ. قبل التعريف الدقيق لنظرية الحاسوبية، علماء الرياضيات غالباً ماكانوا يستخدمون المصطلح غير الرسمي للحساب الفعال Effectively calculable لوصف الوظائف المحسوبة بأساليب ورقة وقلم رصاص. في الثلاثينات من القرن الماضي، بذلت محاولات مستقلة عدة لإضفاء الطابع الرسمي على مفهوم الحاسوبية.

في نظرية الحوسبة، أطروحة تشرش - تورينغ (المعروفة أيضًا باسم أطروحة الحوسبة، أطروحة تورينج - تشيرش، تخمين تشيرش - تورينج، وأطروحة تشيرش، وتخمين تشيرش، وأطروحة تورينج) هي أطروحة حول الطبيعة من الوظائف الحسابية. تنص على أنه يمكن حساب دالة على الأعداد الطبيعية بطريقة فعالة إذا وفقط إذا كانت قابلة للحساب بواسطة آلة تورينج. تمت تسمية الأطروحة على اسم عالم الرياضيات الأمريكي ألونزو تشيرش وعالم الرياضيات البريطاني آلان تورينج. قبل التعريف الدقيق للوظيفة الحسابية، غالبًا ما استخدم علماء الرياضيات المصطلح غير الرسمي القابل للحساب بشكل فعال لوصف الوظائف التي يمكن حسابها بطرق الورق والقلم. في الثلاثينيات من القرن الماضي، جرت عدة محاولات مستقلة لإضفاء الطابع الرسمي على مفهوم الحوسبة:

 في عام 1933، قام كورت جودل، مع جاك هيربراند، بإضفاء الطابع الرسمي على تعريف فئة الوظائف العودية العامة: أصغر فئة من الوظائف (مع العديد من الحجج بشكل تعسفي) التي يتم إغلاقها تحت التكوين والتكرار والتقليل، وتتضمن صفرًا، وكل التوقعات.
 في عام 1936، أنشأ ألونزو تشيرش طريقة لتحديد الوظائف تسمى حساب التفاضل والتكامل. داخل حساب التفاضل والتكامل λ، حدد ترميزًا للأعداد الطبيعية يسمى أرقام تشيرش. تسمى الوظيفة على الأرقام الطبيعية تكامل لامدا  إذا كان من الممكن تمثيل الوظيفة المقابلة في أرقام تشيرش بمصطلح λ-calculus.
 أيضًا في عام 1936، قبل تعلم عمل تشرش،  ابتكر آلان تورينج نموذجًا نظريًا للآلات، تسمى الآن آلات تورينج، والتي يمكنها إجراء حسابات من المدخلات عن طريق التلاعب بالرموز الموجودة على شريط. بالنظر إلى تشفير مناسب للأرقام الطبيعية كتسلسل من الرموز، فإن الوظيفة الموجودة على الأرقام الطبيعية تسمى تورينغ القابلة للحساب إذا كانت بعض آلات تورينغ تحسب الوظيفة المقابلة على الأرقام الطبيعية المشفرة.

أثبتت تشيرش وكلين وتورينغ  [11] أن هذه الفئات الثلاثة المحددة رسميًا للوظائف الحسابية تتطابق: الوظيفة قابلة للحساب λ إذا وفقط إذا كانت تورينغ قابلة للحساب، وإذا وفقط إذا إنه تكراري عام. وقد دفع هذا علماء الرياضيات وعلماء الكمبيوتر إلى الاعتقاد بأن مفهوم الحوسبة يتميز بدقة بهذه العمليات المكافئة الثلاث. المحاولات الرسمية الأخرى لوصف القدرة الحسابية عززت هذا الاعتقاد لاحقًا (انظر أدناه). من ناحية أخرى، تنص أطروحة تشيرش - تورينغ على أن الفئات الثلاث المحددة رسميًا للوظائف الحسابية تتوافق مع المفهوم غير الرسمي لوظيفة قابلة للحساب بشكل فعال. على الرغم من أن الأطروحة تحظى بقبول شبه عالمي، إلا أنه لا يمكن إثباتها رسميًا لأن مفهوم إمكانية الحساب الفعال لا يتم تعريفه إلا بشكل غير رسمي. منذ نشأتها، نشأت اختلافات في الأطروحة الأصلية، بما في ذلك عبارات حول ما يمكن أن يتحقق جسديًا بواسطة الكمبيوتر في عالمنا (أطروحة تشيرش - تورنج المادية) وما يمكن حسابه بكفاءة (أطروحة تشيرش - تورينج (نظرية التعقيد)). لا تعود هذه الاختلافات إلى تشيرش أو تورينج، ولكنها تنشأ من العمل اللاحق في نظرية التعقيد والفيزياء الرقمية. الأطروحة لها أيضًا آثار على فلسفة العقل.

بيان تشيرش وتورنج 
في ما يلي، ستعني الكلمات «قابلة للحساب بشكل فعال» «تم إنتاجها بأي وسيلة» فعالة «حدسية على الإطلاق» و «قابلة للحساب بشكل فعال» ستعني «تم إنتاجها بواسطة آلة توريتغ أو جهاز ميكانيكي مكافئ». «تعريفات» تورينج الواردة في حاشية في رسالة الدكتوراه عام 1938. أطروحة أنظمة المنطق على أساس الترتيب، وتشرف عليها تشيرش، هي نفسها تقريبًا: سنستخدم تعبير «وظيفة قابلة للحساب» للإشارة إلى دالة يمكن حسابها بواسطة آلة، وندع «قابلة للحساب بشكل فعال» تشير إلى الفكرة البديهية دون تحديد محدد مع أي من هذه التعريفات.يمكن ذكر الأطروحة على النحو التالي: كل دالة قابلة للحساب بشكل فعال هي وظيفة قابلة للحساب. صرح تشيرش أيضًا أنه «لن يتم اعتبار أي إجراء حسابي كخوارزمية ما لم يتم تمثيله كآلة تورينج».  صرح تورينج بذلك على النحو التالي:قيل ... أن «دالة قابلة للحساب بشكل فعال إذا كان من الممكن العثور على قيمها من خلال عملية ميكانيكية بحتة». قد نأخذ هذا حرفياً، ونفهم أنه من خلال عملية ميكانيكية بحتة، يمكن تنفيذها بواسطة آلة. التطور ... يؤدي إلي ... لتحديد الحاسوبية  مع الحسابية فعالة. [  هي الحاشية المقتبسة أعلاه. ]

التاريخ 
إحدى المشكلات المهمة التي واجهها علماء المنطق في ثلاثينيات القرن الماضي كانت مشكلة مسألة القرار  لديفيد هيلبرت وويلهلم أكرمان، والتي تساءلت عما إذا كان هناك إجراء ميكانيكي لفصل الحقائق الرياضية عن الأكاذيب الرياضية. تطلب هذا المسعى أن يتم تثبيت فكرة «الخوارزمية» أو «القابلية للحساب الفعال»، على الأقل بشكل كافٍ لبدء المهمة. لكن منذ البداية بدأت محاولات ألونزو تشيرش بجدل مستمر حتى يومنا هذا.  فكرة «القابلية للحساب الفعال» لتكون (1) «بديهية أو بديهية» في نظام بديهي، (2) مجرد تعريف «حدد» اثنين أو أكثر من الافتراضات، (3) فرضية تجريبية لتكون التحقق من خلال ملاحظة الأحداث الطبيعية، أو (4) مجرد اقتراح من أجل الجدل (أي «أطروحة»).

فترة 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». أخيرًا، استخدم كلاين لأول مرة مصطلح «أطروحة تشيرش - تورينج» في قسم يساعد فيه على تقديم توضيحات للمفاهيم الواردة في ورقة ألان تورينج «مشكلة الكلمة في شبه المجموعات مع الإلغاء»، كما هو مطلوب في نقد من ويليام بون.

التطورات اللاحقة 
أدت محاولة فهم فكرة «الحوسبة الفعالة» بشكل أفضل إلى قيام روبن غاندي (تلميذ وصديق تورينج) في عام 1980 بتحليل حساب الآلة (على عكس الحوسبة البشرية التي تقوم بها آلة تورينج). أدى فضول غاندي حول الأوتوماتا الخلوية وتحليلها (بما في ذلك لعبة الحياة لكونواي) والتوازي والأوتوماتا البلورية، إلى اقتراح أربعة «مبادئ (أو قيود) ... وهو ما يقال، يجب أن ترضي أي آلة». رابعه الأكثر أهمية، «مبدأ السببية» يقوم على «السرعة المحدودة لانتشار التأثيرات والإشارات؛ الفيزياء المعاصرة ترفض إمكانية الفعل اللحظي عن بعد». من هذه المبادئ وبعض القيود الإضافية - (1 أ) حد أدنى على الأبعاد الخطية لأي جزء من الأجزاء، (1 ب) حد أعلى لسرعة الانتشار (سرعة الضوء)، (2) التقدم المنفصل للآلة، و (3) السلوك الحتمي - أنتج نظرية مفادها أن «ما يمكن حسابه بواسطة جهاز يفي بالمبادئ من الأول إلى الرابع يمكن حسابه.»  في أواخر التسعينيات، حلل ويلفريد سيغ مفاهيم تورينج وغاندي عن «القابلية للحساب الفعال» بقصد «شحذ المفهوم غير الرسمي، وصياغة سماته العامة بشكل بديهي، والتحقيق في الإطار البديهية». في كتابه عامي 1997 و 2002 عمل يعرض زيغ سلسلة من القيود على سلوك كومبيوتر - «وكيل البشرية الحوسبة الذي ينطلق ميكانيكيا». تختصر هذه القيود إلى:

 "(B.1) (الإصرار) يوجد حد ثابت لعدد التكوينات الرمزية التي يمكن أن يتعرف عليها الكمبيوتر على الفور.
 "(B.2) (الإصرار) هناك حد ثابت لعدد الحالات الداخلية التي يمكن أن يكون الكمبيوتر فيها.
 "(L.1) (المنطقة المحلية) يستطيع الكمبيوتر فقط تغيير عناصر التكوين الرمزي المرصود.
 "(L.2) (المنطقة المحلية) يمكن للمُحسِّن تحويل الانتباه من تكوين رمزي إلى آخر، ولكن يجب أن تكون التكوينات الجديدة التي تمت ملاحظتها ضمن مسافة محدودة من التكوين الذي تمت ملاحظته مسبقًا على الفور.
 «(D) (التحديد) يحدد التكوين (الفرعي) الذي يمكن التعرف عليه فورًا بشكل فريد خطوة الحساب التالية (والمعرف [الوصف الفوري])»؛ ذكر بطريقة أخرى: «الحالة الداخلية للحاسب مع التكوين الملحوظ تعمل بشكل فريد على إصلاح خطوة الحساب التالية والحالة الداخلية التالية.»

يبقى الأمر قيد المناقشة النشطة داخل المجتمع الأكاديمي.

الأطروحة كتعريف 
لا يمكن اعتبار الأطروحة سوى تعريف رياضي عادي. تشير تعليقات جوديل على الموضوع إلى وجهة النظر هذه، على سبيل المثال «تم تحديد التعريف الصحيح للحسابات الميكانيكية بما لا يدع مجالاً للشك بواسطة تورينج». تم تقديم قضية عرض الأطروحة على أنها ليست أكثر من تعريف صريحًا بواسطة روبرت سواري، حيث قيل أيضًا أن تعريف تورينج للقدرة الحسابية ليس أقل احتمالًا أن يكون صحيحًا من تعريف إبسيلون-دلتا للمتصل المستمر. وظيفة.

نجاح الرسالة 
تم اقتراح أشكال أخرى (إلى جانب العودية، حساب التفاضل والتكامل، وآلة تورينج) لوصف إمكانية الحساب / الحوسبة الفعالة. يضيف ستيفن كلاين (1952) إلى القائمة الوظائف " المعقولية في النظام S 1 " لكورت جودل 1936، وأنظمة إميل بوست (1943، 1946) «تشيرش وتسمى أيضًا الأنظمة العادية». في الخمسينيات من القرن الماضي، قام هاو وانج ومارتن ديفيس بتبسيط نموذج آلة تورينج ذات الشريط الواحد (انظر آلة ما بعد تورينج). قام مارفن مينسكي بتوسيع النموذج ليشمل شريطين أو أكثر وقام بتبسيط الأشرطة بشكل كبير إلى «عدادات مقلوبة»، والتي طورها ميلزاك ولامبك إلى ما يعرف الآن باسم نموذج آلة العداد. في أواخر الستينيات وأوائل السبعينيات من القرن الماضي، قام الباحثون بتوسيع نموذج آلة العداد إلى آلة التسجيل، وهي قريبة قريبة من المفهوم الحديث للكمبيوتر. تشمل النماذج الأخرى المنطق التوافقي وخوارزميات ماركوف. يضيف جورخيف نموذج آلة المؤشر لكولموغوروف ويوسبنكي (1953، 1958): «... لقد أرادوا ذلك فقط ... أقنعوا أنفسهم بأنه لا توجد طريقة لتوسيع مفهوم الوظيفة الحسابية.» 

تتضمن كل هذه المساهمات أدلة على أن النماذج مكافئة حسابيًا لآلة تورينج؛ ويقال أن هذه النماذج قد اكتملت تورينج. نظرًا لأن كل هذه المحاولات المختلفة لإضفاء الطابع الرسمي على مفهوم «الحساب الفعال / الحوسبة» قد أسفرت عن نتائج معادلة، فمن المفترض الآن بشكل عام أن أطروحة تشيرش-تورينج صحيحة. في الواقع، اقترح جوديل (1936) شيئًا أقوى من هذا؛ لاحظ أن هناك شيئًا «مطلقًا» حول مفهوم "معقول في S 1 ":

الاستخدام غير الرسمي في البراهين 
غالبًا ما تستدعي البراهين في نظرية الحوسبة أطروحة تشيرش-تورينغ بطريقة غير رسمية لتأسيس قابلية حساب الوظائف مع تجنب التفاصيل (الطويلة جدًا غالبًا) التي قد تكون متضمنة في إثبات رسمي صارم. لإثبات أن الوظيفة قابلة للحساب بواسطة آلة تورينج، يُعتبر عادةً كافيًا إعطاء وصف إنكليزي غير رسمي لكيفية حساب الوظيفة بفعالية، ثم استنتاج «من خلال أطروحة تشيرش تورينج» أن الوظيفة قابلة للحساب (بالتساوي)، متكرر جزئي). يعطي ديرك فان دالين المثال التالي من أجل توضيح هذا الاستخدام غير الرسمي لأطروحة تشيرش - تورينغ. من أجل جعل المثال أعلاه صارمًا تمامًا، يجب على المرء أن يبني بعناية آلة تورينج، أو دالة، أو يستدعي بعناية بديهيات العودية، أو في أفضل الأحوال، يستدعي بذكاء نظريات مختلفة لنظرية الحوسبة. ولكن نظرًا لأن مُنظِّر الحوسبة يعتقد أن قابلية تورينج الحوسبية تلتقط بشكل صحيح ما يمكن حسابه بشكل فعال، ولأن الإجراء الفعال مكتوب باللغة الإنجليزية لتحديد المجموعة ب، فإن منظري الحوسبة يقبل هذا كدليل على أن المجموعة عودية بالفعل.

الاختلافات 
دفع نجاح أطروحة تشيرش - تورينغ إلى اقتراح اختلافات في الأطروحة. على سبيل المثال، تنص أطروحة تشيرش - تورينج الفيزيائية على أن: "جميع الوظائف المحسوبة فيزيائيًا قابلة للحساب من قبل تورينج."   لا تذكر أطروحة تشيرش تورينج شيئًا عن الكفاءة التي يمكن بها لأحد النماذج الحسابية محاكاة نموذج آخر. لقد ثبت على سبيل المثال أن آلة تورينغ العامة (متعددة الأشرطة) تعاني فقط من عامل تباطؤ لوغاريتمي في محاكاة أي آلة تورينج. تتناول مجموعة متنوعة من أطروحة تشيرش-تورينج ما إذا كان يمكن محاكاة نموذج حسابي تعسفي ولكن "معقول" بكفاءة. وهذا ما يسمى أطروحة الجدوى، والمعروفة أيضًا باسم أطروحة التعقيد (الكلاسيكية) - تشيرش النظرية - أطروحة تورينج أو أطروحة تشيرش الموسعة - أطروحة تورينج، والتي لا ترجع إلى تشيرش أو تورينج، بل تم تحقيقها تدريجيًا في تطوير نظرية التعقيد. تنص على: " يمكن لآلة تورينج الاحتمالية محاكاة أي نموذج واقعي للحساب بكفاءة." كلمة "فعال" هنا تعني ما يصل إلى تخفيضات كثيرة الحدود. كانت هذه الأطروحة في الأصل تسمى أطروحة التعقيد الحسابي - تشيرش النظرية - تورينج من قبل إيثان برنشتاين وأوميش فازيراني (1997). تفترض أطروحة التعقيد - تشيرش - تورينج النظرية أن جميع نماذج الحساب "المعقولة" تنتج نفس فئة المشكلات التي يمكن حسابها في زمن متعدد الحدود. بافتراض التخمين بأن الوقت متعدد الحدود الاحتمالي (BPP) يساوي وقت كثير الحدود الحتمي (P)، فإن كلمة "احتمالية" اختيارية في أطروحة التعقيد - نظرية تشيرش - تورينج. قدم سيس إف سلوت وبيتر فان إيمدي بوا أطروحة مماثلة، تسمى أطروحة الثبات. وهو ينص على: " معقولة "محاكاة بعضها البعض ضمن ما يحدها من النفقات العامة في وقت والنفقات العامة ثابت عامل في الفضاء."  ظهرت الأطروحة في الأصل في ورقة بحثية في إس تي أو سي 84، والتي كانت أول ورقة توضح أنه يمكن تحقيق وقت متعدد الحدود الزائد والمساحة الثابتة في نفس الوقت لمحاكاة آلة الوصول العشوائي على آلة تورينج.

إذا تم إثبات أن بي كيو بي عبارة عن مجموعة شاملة صارمة من بي بي بي، فسيؤدي ذلك إلى إبطال نظرية التعقيد - نظرية تشيرش - تورينج. بمعنى آخر، ستكون هناك خوارزميات كمومية فعالة تؤدي مهامًا لا تحتوي على خوارزميات احتمالية فعالة. ومع ذلك، فإن هذا لن يبطل أطروحة تشيرش-تورينغ الأصلية، حيث يمكن دائمًا محاكاة الكمبيوتر الكمومي بواسطة آلة تورينج، ولكنه سيبطل نظرية التعقيد الكلاسيكي - نظرية تشيرش - تورينج لأسباب تتعلق بالكفاءة. «يمكن لآلة تورينج الكمومية أن تحاكي أي نموذج واقعي للحساب بكفاءة.»

يزعم يوجين إيبرباخ وبيتر فيجنر أن أطروحة كنيسة-تورينج تُفسَّر أحيانًا على نطاق واسع جدًا، مشيرين إلى «بالرغم من [... ] آلات تورنج تعبر عن سلوك الخوارزميات، والتأكيد على أوسع خوارزميات التقاط بالضبط ما يمكن حسابها غير صالح». يزعمون أن أشكال الحساب التي لم تلتقطها الأطروحة ذات صلة اليوم، وهي المصطلحات التي يسمونها حساب تورينج الفائق.

المضامين الفلسفية 
فسر الفلاسفة أطروحة كنيسة تورينج على أنها لها آثار على فلسفة العقل. يقول ب. جاك كوبلاند أنه سؤال تجريبي مفتوح حول ما إذا كانت هناك عمليات فيزيائية حتمية فعلية والتي، على المدى الطويل، تستعصي على المحاكاة بواسطة آلة تورينج. علاوة على ذلك، يقول إنه سؤال تجريبي مفتوح حول ما إذا كانت أي من هذه العمليات متورطة في عمل الدماغ البشري. هناك أيضًا بعض الأسئلة المفتوحة المهمة التي تغطي العلاقة بين أطروحة تشيرش-تورينغ والفيزياء، وإمكانية الحوسبة المفرطة. عند تطبيقها على الفيزياء، فإن الأطروحة لها عدة معانٍ محتملة:

 الكون يعادل آلة تورينج. وبالتالي، فإن حساب الوظائف غير العودية أمر مستحيل ماديًا. وقد أطلق على هذا اسم أطروحة تشيرش - تورينغ القوية، أو مبدأ تشيرش - تورينج - دويتش، وهو أساس للفيزياء الرقمية.
 الكون ليس يعادل آلة تورينج (أي قوانين الفيزياء لا تورينج محسوب)، ولكن الأحداث المادية غير قابلة للإنضغاط. على سبيل المثال، الكون الذي تتضمن فيه الفيزياء أعدادًا حقيقية عشوائية، في مقابل الحقائق المحسوبة، يقع ضمن هذه الفئة.
 الكون عبارة عن حاسوب فائق، ومن الممكن بناء أجهزة فيزيائية لتسخير هذه الخاصية وحساب الوظائف غير التكرارية. على سبيل المثال، هناك سؤال مفتوح حول ما إذا كانت جميع الأحداث الميكانيكية الكمومية قابلة للحساب من نوع تورينج، على الرغم من أنه من المعروف أن النماذج الصارمة مثل آلات تورينج الكمومية تعادل آلات تورينج الحتمية. (ليست بالضرورة معادلة بشكل فعال ؛ انظر أعلاه.) اقترح جون لوكاس وروجر بنروز أن العقل البشري قد يكون نتيجة لنوع من الحسابات «غير الخوارزمية» المحسنة ميكانيكيًا الكم.

هناك العديد من الاحتمالات التقنية الأخرى التي تقع خارج أو بين هذه الفئات الثلاث، ولكنها تعمل على توضيح نطاق المفهوم. الجوانب الفلسفية للأطروحة، فيما يتعلق بكل من أجهزة الكمبيوتر الفيزيائية والبيولوجية، تمت مناقشتها أيضًا في كتاب أوديفريدي لعام 1989 حول نظرية العودية.

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

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

انظر أيضًا 

 آلة مجردة
 نظرية الحوسبة
 نموذج الحوسبة
 كمال تورنغ

روابط خارجية 
 كتاب "The Church–Turing Thesis".
 كتاب "Computation in Physical Systems" -A معالجة فلسفية شاملة للقضايا ذات الصلة.
 
 تم تخصيص عدد خاص (المجلد 28، العدد 4، 1987) من مجلة نوتردام للمنطق الرسمي لأطروحة تشيرش - تورينغ.

المراجع 

آلان تورنغ
النظرية الحسابية
فلسفة علم الحاسوب
نظرية قابلية الحساب
في نظرية القابلية للحساب ، تعرف أطروحة تشرش - تورنغ Church - Turing Th esis ، أو حدسية تشرش - تورنغ Church - Turing Conjecture ، على أن ها فرضية Hypoth esis حول طبيعة الدوال الحسابية Computable functions . تنص الفرضية على أن الأعداد الطبيعية تكون قابلة للحساب بعقل إنساني وبخوارزمية ، مع تجاهل القيود على الموارد ، إذا وفقط كانت محسوبة ب استخدام آلة تورنغ . الأطروحة سميت على عالم الرياضيات الأمريكي ألونزو تشرش وعالم الرياضيات البريطاني آلان تورنغ . قبل التعريف الدقيق ل نظرية الحاسوبية ، علماء الرياضيات غالباً ما كانوا يستخدمون المصطلح غير الرسمي للحساب الفعال Effectively calculable لوصف الوظائف المحسوبة بأساليب ورقة وقلم رصاص . في الثلاثينات من القرن الماضي ، بذلت محاولات مستقلة عدة لإضفاء الطابع الرسمي على مفهوم الحاسوبية . في نظرية الحوسبة ، أطروحة تشرش - تورينغ ( المعروفة أيضًا ب اسم أطروحة الحوسبة ، أطروحة تورينج - تشيرش ، تخمين تشيرش - تورينج ، وأطروحة تشيرش ، وتخمين تشيرش ، وأطروحة تورينج ) هي أطروحة حول الطبيعة من الوظائف الحسابية . تنص على أن ه يمكن حساب دالة على الأعداد الطبيعية ب طريقة فعالة إذا وفقط إذا كانت قابلة للحساب ب واسطة آلة تورينج . تمت تسمية الأطروحة على اسم عالم الرياضيات الأمريكي ألونزو تشيرش وعالم الرياضيات البريطاني آلان تورينج . قبل التعريف الدقيق للوظيفة الحسابية ، غالبًا ما استخدم علماء الرياضيات المصطلح غير الرسمي القابل للحساب ب شكل فعال لوصف الوظائف التي يمكن حساب ها ب طرق الورق والقلم . في الثلاثينيات من القرن الماضي ، جرت عدة محاولات مستقلة لإضفاء الطابع الرسمي على مفهوم الحوسبة : في عام قام كورت جودل ، مع جاك هيربراند ، بإضفاء الطابع الرسمي على تعريف فئة الوظائف العودية العامة : أصغر فئة من الوظائف ( مع العديد من الحجج ب شكل تعسفي ) التي يتم إغلاق ها تحت التكوين وال تكرار و التقليل ، و تتضمن صفرًا ، و كل التوقعات . في عام أنشأ ألونزو تشيرش طريقة ل تحديد الوظائف تسمى حساب التفاضل و التكامل . داخل حساب التفاضل و التكامل λ ، حدد ترميزًا للأعداد الطبيعية يسمى أرقام تشيرش . تسمى الوظيفة على الأرقام الطبيعية تكامل لامدا إذا كان من الممكن تمثيل الوظيفة المقابلة في أرقام تشيرش بمصطلح λ - c alculus . أيضًا في عام قبل تعلم عمل تشرش ، ابتكر آلان تورينج نموذجًا نظريًا للآلات ، تسمى الآن آلات تورينج ، و التي يمكن ها إجراء حسابات من المدخلات عن طريق التلاعب بالرموز الموجودة على شريط . ب النظر إلى تشفير مناسب للأرقام الطبيعية كتسلسل من الرموز ، ف إن الوظيفة الموجودة على الأرقام الطبيعية تسمى تورينغ القابلة للحساب إذا كانت بعض آلات تورينغ تحسب الوظيفة المقابلة على الأرقام الطبيعية المشفرة . أثبتت تشيرش وكلين وتورينغ [ 11 ] أن هذه الفئات الثلاثة المحددة رسميًا للوظائف الحسابية تتطابق : الوظيفة قابلة للحساب λ إذا وفقط إذا كانت تورينغ قابلة للحساب ، و إذا وفقط إذا إن ه تكرار ي عام . و قد دفع هذا علماء الرياضيات و علماء الكمبيوتر إلى الاعتقاد ب أن مفهوم الحوسبة يتميز ب دقة ب هٰذه العمليات المكافئة الثلاث . المحاولات الرسمية الأخرى لوصف القدرة الحسابية عززت هذا الاعتقاد لاحقًا ( انظر أدنا ه ) . من ناحية أخرى ، تنص أطروحة تشيرش - تورينغ على أن الفئات الثلاث المحددة رسميًا للوظائف الحسابية تتوافق مع المفهوم غير الرسمي لوظيفة قابلة للحساب ب شكل فعال . على الرغم من أن الأطروحة تحظى ب قبول شبه عالمي ، إلا أن ه لا يمكن إثبات ها رسميًا لأن مفهوم إمكانية الحساب الفعال لا يتم تعريف ه إلا ب شكل غير رسمي . منذ نشأت ها ، نشأت اختلافات في الأطروحة الأصلية ، ب ما في ذلك عبارات حول ما يمكن أن يتحقق جسديًا ب واسطة الكمبيوتر في عالم نا ( أطروحة تشيرش - تورنج المادية ) و ما يمكن حساب ه بكفاءة ( أطروحة تشيرش - تورينج ( نظرية التعقيد ) ) . لا تعود هذه الاختلافات إلى تشيرش أو تورينج ، و لٰكن ها تنشأ من العمل اللاحق في نظرية التعقيد والفيزياء الرقمية . الأطروحة ل ها أيضًا آثار على فلسفة العقل . بيان تشيرش وتورنج في ما يلي ، ستعني الكلمات « قابلة للحساب ب شكل فعال » « تم إنتاج ها ب أي وسيلة » فعالة « حدسية على الإطلاق » و « قابلة للحساب ب شكل فعال » ستعني « تم إنتاج ها ب واسطة آلة توريتغ أو جهاز ميكانيكي مكافئ » . « تعريفات » تورينج الواردة في حاشية في رسالة الدكتورا ه عام أطروحة أنظمة المنطق على أساس الترتيب ، وتشرف علي ها تشيرش ، هي نفس ها تقريبًا : سنستخدم تعبير « وظيفة قابلة للحساب » للإشارة إلى دالة يمكن حساب ها ب واسطة آلة ، وندع « قابلة للحساب ب شكل فعال » تشير إلى الفكرة البديهية دون تحديد محدد مع أي من هذه التعريفات . يمكن ذكر الأطروحة على النحو التالي : كل دالة قابلة للحساب ب شكل فعال هي وظيفة قابلة للحساب . صرح تشيرش أيضًا أن ه « لن يتم اعتبار أي إجراء حسابي كخوارزمية ما لم يتم تمثيل ه كآلة تورينج » . صرح تورينج ب ذٰلك على النحو التالي : قيل . . . أن « دالة قابلة للحساب ب شكل فعال إذا كان من الممكن العثور على قيم ها من خلال عملية ميكانيكية بحتة » . قد نأخذ هذا حرفياً ، ونفهم أن ه من خلال عملية ميكانيكية بحتة ، يمكن تنفيذ ها ب واسطة آلة . التطور . . . يؤدي إلي . . . ل تحديد الحاسوبية مع الحسابية فعالة . [ هي الحاشية المقتبسة أعلا ه . ] التاريخ إحدى المشكلات المهمة التي واجه ها علماء المنطق في ثلاثينيات القرن الماضي كانت مشكلة مسألة القرار لديفيد هيلبرت وويلهلم أكرمان ، و التي تساءلت عن ما إذا كان هناك إجراء ميكانيكي ل فصل الحقائق الرياضية عن الأكاذيب الرياضية . تطلب هذا المسعى أن يتم تثبيت فكرة « الخوارزمية » أو « القابلية للحساب الفعال » ، على الأقل ب شكل كافٍ ل بدء المهمة . لكن منذ البداية بدأت محاولات ألونزو تشيرش بجدل مستمر حتى يوم نا هذا . فكرة « القابلية للحساب الفعال » ل تكون « بديهية أو بديهية » في نظام بديهي ، مجرد تعريف « حدد » اثنين أو أكثر من الافتراضات ، فرضية تجريبية ل تكون التحقق من خلال ملاحظة الأحداث الطبيعية ، أو مجرد اقتراح من أجل الجدل ( أي « أطروحة » ) . فترة في سياق دراسة المشكلة ، قدم تشرش وتلميذ ه ستيفن كلاين مفهوم الوظائف القابلة لل تحديد ، وتمكنا من إثبات أن العديد من الفئات الكبيرة من الوظائف التي يتم مواجهت ها ب شكل متكرر في نظرية الأعداد كانت قابلة لل تحديد λ . بدأ النقاش عندما اقترحت تشيرش على جودل أن على المرء أن يعرف الوظائف « القابلة للحساب ب شكل فعال » كوظائف قابلة لل تحديد λ . و مع ذلك ، لم يكن جودل مقتنعًا و وصف الاقتراح ب أن ه « غير مرض تمامًا » . بدلاً من ذلك ، في المراسلات مع تشيرش ( حوالي اقترح جودل إضفاء البديهية على مفهوم « الحساب الفعال » . في الواقع ، في رسالة أرسل ها تشرش عام إلى كلاين ، أفاد تشرش ب أن : لكن جودل لم يقدم أي إرشادات أخرى . في النهاية ، كان يقترح تكرار ه ، بعد تعديل ه من خلال اقتراح هيربراند ، الذي ذكر ه جودل ب التفصيل في محاضرات ه عامفي برينستون نيوجيرسي ( قام كلاين وروسر بنسخ الملاحظات ) . لٰكن ه لم يعتقد أن ه يمكن تحديد الفكرتين ب شكل مرضٍ « إلا ب طريقة الكشف عن مجريات الأمور » . بعد ذلك ، كان من الضروري تحديد و إثبات تكافؤ مفهومين ل القدرة على الحساب الفعال . مُجهزًا ب حساب التفاضل و التكامل λ و العودة « العامة » ، قدم ستيفن كلاين ب مساعدة تشرش وجي باركلي روسر البراهينل إثبات أن الحسابين متكافئان . قام تشرش بعد ذلك بتعديل أساليب ه ل تشمل استخدام عودية هيربراند - جودل ثم أثبتأن مسألة القرار غير قابل ل الحل : لا توجد خوارزمية يمكن ها تحديد ما إذا كانت الصيغة جيدة التكوين . بعد عدة سنوات في رسالة إلى ديفيس ( حوالي قال جودل إن ه « في وقت هذه المحاضرات [ 1934 ] ، لم يكن مقتنعًا على الإطلاق ب أن مفهوم ه لل تكرار يشمل جميع عمليات ال تكرار الممكنة » . ب حلول عام - تنصل جودل من تكرار هيربراند - جودل و حساب التفاضل و التكامل ل صالح آلة تورينج كتعريف لـ « الخوارزمية » أو « الإجراء الميكانيكي » أو « النظام الرسمي » . فرضية تؤدي إلى قانون طبيعي ؟ : في أواخر عام تم تسليم ورقة آلان تورينج ( التي تثبت أيضًا أن مشكلة مسألة القرار غير قابلة ل الحل ) شفهيًا ، و لٰكن ها لم تظهر بعد في الطباعة . من ناحية أخرى ، ظهرت ورقة E mil Post لعاموتم اعتماد ها ب شكل مستقل عن عمل تورينج . اختلف بوست ب شدة مع « تحديد » تشيرش للحساب الفعال ب استخدام حساب التفاضل و التكامل λ وال تكرار . بدلاً من ذلك ، اعتبر فكرة « القابلية للحساب الفعال » مجرد « فرضية عمل » قد تؤدي بالاستدلال الاستقرائي إلى « قانون طبيعي » بدلاً من « تعريف أو بديهية » . انتقدت تشيرش هذه الفكرة « ب شدة » . وهكذا كان بوست في ورقت ه البحثية عاميستبعد أيضًا اقتراح كورت جودل للكنتش فيبأن الأطروحة يمكن التعبير عن ها كبديهية أو مجموعة من البديهيات . يضيف تورينج تعريفًا آخر ، يساوي روسر الثلاثة : في غضون وقت قصير فقط ، ظهرت ورقة تورينج « حول الأرقام المحسوبة ، مع تطبيق على مشكلة مسألة القرار » . ذكر في ه فكرة أخرى عن « الحوسبة الفعالة » مع إدخال آلات ه ( المعروفة الآن ب اسم النموذج الحسابي ال مجرد لآلة تورينج ) . و في رسم إثبات تمت إضافت ه ب اعتبار ه « ملحقًا » إلى ورقت ه البحثية أظهر تورينج أن فئات الوظائف المحددة ب واسطة حساب التفاضل و التكامل λ وآلات تورينج تتطابق . كان تشرش سريعًا في إدراك مدى جاذبية تحليل تورينج . في مراجعت ه لورقة تورينج أوضح أن فكرة تورينج جعلت « التماثل بفعالية في المعنى العادي ( غير المحدد صراحة ) واضحًا على الفور » . في غضون بضع سنواتس يقترح تورينج ، مثل تشرش وكلين من قبل ه ، أن تعريف ه الرسمي لعامل الحوسبة الميكانيكية هو التعريف الصحيح . وهكذا ، ب حلول عام اقترحت كل من تشيرشوتورنج ب شكل فردي أن « الأنظمة الرسمية » يجب أن تكون تعريفات « للحساب الفعال » . أطروحة تشرش - تورينغ : ستيفن كلاين ، في مقدمة عن الرياضيات ، انتقل أخيرًا إلى تسمية « أطروحة تشيرش » و « أطروحة تورينج » ، مستخدمًا نظرية ه في القابلية لل تكرار . بعد أن تحول كلاين من تقديم عمل ه في مصطلحات تعريف تشيرش - كلين لامدا ، إلى ال تكرار العودي جودل - كلين ( الوظائف العودية الجزئية ) . في هذا الانتقال ، عدل كلين وظائف جوديل العودية العامة ل السماح ب إثبات عدم قابلية حل المشكلات في حدس آي جي براور . في كتاب ه للخريجين حول المنطق ، تم تقديم « أطروحة تشيرش » وتبيّن أن النتائج الرياضية الأساسية غير قابلة ل التحقيق . بعد ذلك ، يواصل كلاين تقديم « أطروحة تورينج » ، حيث تظهر النتائج على أن ها غير قابلة للحساب ، مستخدمًا اشتقاق ه المبسط لآلة تورينج بناءً على عمل إميل بوست . تم إثبات تكافؤ كلتا الأطروحتين ب استخدام « نظرية XXX » . أخيرًا ، استخدم كلاين ل أول مرة مصطلح « أطروحة تشيرش - تورينج » في قسم يساعد في ه على تقديم توضيحات للمفاهيم الواردة في ورقة ألان تورينج « مشكلة الكلمة في شبه المجموعات مع ال إلغاء » ، كما هو مطلوب في نقد من ويليام بون . التطورات اللاحقة أدت محاولة ف هم فكرة « الحوسبة الفعالة » ب شكل أفضل إلى قيام روبن غاندي ( تلميذ وصديق تورينج ) في عامب تحليل حساب الآلة ( على عكس الحوسبة البشرية التي تقوم ب ها آلة تورينج ) . أدى فضول غاندي حول الأوتوماتا الخلوية وتحليل ها ( ب ما في ذلك لعبة الحياة لكونواي ) والتوازي والأوتوماتا البلورية ، إلى اقتراح أربعة « مبادئ ( أو قيود ) . . . و هو ما يقال ، يجب أن ترضي أي آلة » . رابع ه الأكثر أهمية ، « مبدأ السببية » يقوم على « السرعة المحدودة ل انتشار التأثيرات والإشارات ؛ الفيزياء المعاصرة ترفض إمكانية الفعل اللحظي عن بعد » . من هذه المبادئ و بعض القيود الإضافية - أ ) حد أدنى على ال أبعاد الخطية ل أي جزء من ال أجزاء ،ب ) حد أعلى ل سرعة الانتشار ( سرعة الضوء ) ، التقدم المنفصل للآلة ، والسلوك الحتمي - أنتج نظرية مفاد ها أن « ما يمكن حساب ه ب واسطة جهاز يفي بالمبادئ من الأول إلى الرابع يمكن حساب ه . » في أواخر التسعينيات ، حلل ويلفريد سيغ مفاهيم تورينج وغاندي عن « القابلية للحساب الفعال » ب قصد « شحذ المفهوم غير الرسمي ، وصياغة سمات ه العامة ب شكل بديهي ، و التحقيق في الإطار البديهية » . في كتاب ه عاميوعمل يعرض زيغ سلسلة من القيود على سلوك كومبيوتر - « وكيل البشرية الحوسبة الذي ينطلق ميكانيكيا » . تختصر هذه القيود إلى : " ( B.1 ) ( الإصرار ) يوجد حد ثابت ل عدد التكوينات الرمزية التي يمكن أن يتعرف علي ها الكمبيوتر على الفور . " ( B.2 ) ( الإصرار ) هناك حد ثابت ل عدد الحالات الداخلية التي يمكن أن يكون الكمبيوتر في ها . " ( L.1 ) ( المنطقة المحلية ) يستطيع الكمبيوتر فقط تغيير عناصر التكوين الرمزي المرصود . " ( L.2 ) ( المنطقة المحلية ) يمكن للمُحسِّن تحويل الانتباه من تكوين رمزي إلى آخر ، و لٰكن يجب أن تكون التكوينات الجديدة التي تمت ملاحظة ها ضمن مسافة محدودة من التكوين الذي تمت ملاحظته مسبقًا على الفور . « ( D ) ( ال تحديد ) يحدد التكوين ( الفرعي ) الذي يمكن التعرف علي ه فورًا ب شكل فريد خطوة الحساب التالية ( والمعرف [ الوصف الفوري ] ) » ؛ ذكر ب طريقة أخرى : « الحالة الداخلية للحاسب مع التكوين الملحوظ تعمل ب شكل فريد على إصلاح خطوة الحساب التالية والحالة الداخلية التالية . » يبقى الأمر قيد ا المناقشة النشطة داخل المجتمع الأكاديمي . الأطروحة كتعريف لا يمكن اعتبار الأطروحة سوى تعريف رياضي عادي . تشير تعليقات جوديل على الموضوع إلى وجهة النظر هذه ، على سبيل المثال « تم تحديد التعريف الصحيح للحسابات الميكانيكية ب ما لا يدع مجالاً للشك ب واسطة تورينج » . تم تقديم قضية عرض الأطروحة على أن ها ليست أكثر من تعريف صريحًا ب واسطة روبرت سواري ، حيث قيل أيضًا أن تعريف تورينج ل القدرة الحسابية ليس أقل احتمالًا أن يكون صحيحًا من تعريف إبسيلون - دلتا للمتصل المستمر . وظيفة . نجاح الرسالة تم اقتراح أشكال أخرى ( إلى جانب العودية ، حساب التفاضل و التكامل ، وآلة تورينج ) لوصف إمكانية الحساب / الحوسبة الفعالة . يضيف ستيفن كلاين إلى القائمة الوظائف " المعقولية في النظام S " لكورت جودل وأنظمة إميل بوست « تشيرش وتسمى أيضًا الأنظمة العادية » . في الخمسينيات من القرن الماضي ، قام هاو وانج ومارتن ديفيس ب تبسيط نموذج آلة تورينج ذات الشريط الواحد ( انظر آلة ما بعد تورينج ) . قام مارفن مينسكي ب توسيع النموذج ل يشمل شريطين أو أكثر و قام ب تبسيط الأشرطة ب شكل كبير إلى « عدادات مقلوبة » ، و التي طور ها ميلزاك ولامبك إلى ما يعرف الآن ب اسم نموذج آلة العداد . في أواخر الستينيات وأوائل السبعينيات من القرن الماضي ، قام الباحثون ب توسيع نموذج آلة العداد إلى آلة التسجيل ، و هي قريبة قريبة من المفهوم الحديث للكمبيوتر . تشمل النماذج الأخرى المنطق التوافقي وخوارزميات ماركوف . يضيف جورخيف نموذج آلة المؤشر لكولموغوروف ويوس بنكي « . . . لقد أرادوا ذلك فقط . . . أقنعوا أنفس هم ب أن ه لا توجد طريقة ل توسيع مفهوم الوظيفة الحسابية . » تتضمن كل هذه المساهمات أدلة على أن النماذج مكافئة حسابيًا لآلة تورينج ؛ ويقال أن هذه النماذج قد اكتملت تورينج . نظرًا لأن كل هذه المحاولات المختلفة لإضفاء الطابع الرسمي على مفهوم « الحساب الفعال / الحوسبة » قد أسفرت عن نتائج معادلة ، ف من المفترض الآن ب شكل عام أن أطروحة تشيرش - تورينج صحيحة . في الواقع ، اقترح جوديلشيئًا أقوى من هذا ؛ لاحظ أن هناك شيئًا « مطلقًا » حول مفهوم " معقول في S " : الاستخدام غير الرسمي في البراهين غالبًا ما تستدعي البراهين في نظرية الحوسبة أطروحة تشيرش - تورينغ ب طريقة غير رسمية ل تأسيس قابلية حساب الوظائف مع تجنب التفاصيل ( الطويلة جدًا غالبًا ) التي قد تكون متضمنة في إثبات رسمي صارم . ل إثبات أن الوظيفة قابلة للحساب ب واسطة آلة تورينج ، يُعتبر عادةً كافيًا إعطاء وصف إنكليزي غير رسمي لكيفية حساب الوظيفة بفعالية ، ثم استنتاج « من خلال أطروحة تشيرش تورينج » أن الوظيفة قابلة للحساب ( بالتساوي ) ، متكرر جزئي ) . يعطي ديرك ف إن دالين المثال التالي من أجل توضيح هذا الاستخدام غير الرسمي لأطروحة تشيرش - تورينغ . من أجل جعل المثال أعلا ه صارمًا تمامًا ، يجب على المرء أن يبني ب عناية آلة تورينج ، أو دالة ، أو يستدعي ب عناية بديهيات العودية ، أو في أفضل الأحوال ، يستدعي ب ذكاء نظريات مختلفة ل نظرية الحوسبة . و لٰكن نظرًا لأن مُنظِّر الحوسبة يعتقد أن قابلية تورينج الحوسبية تلتقط ب شكل صحيح ما يمكن حساب ه ب شكل فعال ، و لأن الإجراء الفعال مكتوب باللغة الإنجليزية ل تحديد المجموعة ب ، ف إن منظري الحوسبة يقبل هذا ك دليل على أن المجموعة عودية ب الفعل . الاختلافات دفع نجاح أطروحة تشيرش - تورينغ إلى اقتراح اختلافات في الأطروحة . على سبيل المثال ، تنص أطروحة تشيرش - تورينج الفيزيائية على أن : " جميع الوظائف المحسوبة فيزيائيًا قابلة للحساب من قبل تورينج . " لا تذكر أطروحة تشيرش تورينج شيئًا عن الكفاءة التي يمكن ب ها ل أحد النماذج الحسابية محاكاة نموذج آخر . لقد ثبت على سبيل المثال أن آلة تورينغ العامة ( متعددة الأشرطة ) تعاني فقط من عامل تباطؤ لوغاريتمي في محاكاة أي آلة تورينج . تتناول مجموعة متنوعة من أطروحة تشيرش - تورينج ما إذا كان يمكن محاكاة نموذج حسابي تعسفي و لٰكن " معقول " بكفاءة . و هٰذا ما يسمى أطروحة الجدوى ، والمعروفة أيضًا ب اسم أطروحة التعقيد ( الكلاسيكية ) - تشيرش ال نظرية - أطروحة تورينج أو أطروحة تشيرش ال موسعة - أطروحة تورينج ، و التي لا ترجع إلى تشيرش أو تورينج ، بل تم تحقيق ها تدريجيًا في تطوير نظرية التعقيد . تنص على : " يمكن لآلة تورينج الاحتمالية محاكاة أي نموذج واقعي للحساب بكفاءة . " كلمة " فعال " هنا تعني ما يصل إلى تخفيضات كثيرة الحدود . كانت هذه الأطروحة في الأصل تسمى أطروحة التعقيد الحسابي - تشيرش ال نظرية - تورينج من قبل إيثان برنشتاين وأوميش فازيراني تفترض أطروحة التعقيد - تشيرش - تورينج ال نظرية أن جميع نماذج الحساب " المعقولة " تنتج نفس فئة المشكلات التي يمكن حساب ها في زمن متعدد الحدود . بافتراض التخمين ب أن الوقت متعدد الحدود الاحتمالي ( BPP ) يساوي وقت كثير الحدود الحتمي ( P ) ، ف إن كلمة " احتمالية " اختيارية في أطروحة التعقيد - نظرية تشيرش - تورينج . قدم سيس إف سلوت وبيتر ف إن إيمدي بوا أطروحة مماثلة ، تسمى أطروحة الثبات . و هو ينص على : " معقولة " محاكاة بعض ها البعض ضمن ما يحد ها من النفقات العامة في وقت والنفقات العامة ثابت عامل في الفضاء . " ظهرت الأطروحة في الأصل في ورقة بحثية في إس تي أو سي و التي كانت أول ورقة توضح أن ه يمكن تحقيق وقت متعدد الحدود الزائد والمساحة الثابتة في نفس الوقت لمحاكاة آلة الوصول العشوائي على آلة تورينج . إذا تم إثبات أن بي كيو بي عبارة عن مجموعة شاملة صارمة من بي بي بي ، فس يؤدي ذلك إلى إبطال نظرية التعقيد - نظرية تشيرش - تورينج . ب معنى آخر ، س تكون هناك خوارزميات كمومية فعالة تؤدي مهامًا لا تحتوي على خوارزميات احتمالية فعالة . و مع ذلك ، ف إن هذا لن يبطل أطروحة تشيرش - تورينغ الأصلية ، حيث يمكن دائمًا محاكاة الكمبيوتر الكمومي ب واسطة آلة تورينج ، و لٰكن ه سيبطل نظرية التعقيد الكلاسيكي - نظرية تشيرش - تورينج ل أسباب تتعلق ب الكفاءة . « يمكن لآلة تورينج الكمومية أن تحاكي أي نموذج واقعي للحساب بكفاءة . » يزعم يوجين إيبرباخ وبيتر فيجنر أن أطروحة كنيسة - تورينج تُفسَّر أحيانًا على نطاق واسع جدًا ، مشيرين إلى « ب الرغم من [ . . . ] آلات تورنج تعبر عن سلوك الخوارزميات ، و التأكيد على أوسع خوارزميات التقاط ب الضبط ما يمكن حساب ها غير صالح » . يزعمون أن أشكال الحساب التي لم تلتقط ها الأطروحة ذات صلة اليوم ، و هي المصطلحات التي يسمون ها حساب تورينج الفائق . المضامين الفلسفية فسر الفلاسفة أطروحة كنيسة تورينج على أن ها ل ها آثار على فلسفة العقل . يقول ب . جاك كوبلاند أن ه سؤال تجريبي مفتوح حول ما إذا كانت هناك عمليات فيزيائية حتمية فعلية و التي ، على المدى الطويل ، تستعصي على المحاكاة ب واسطة آلة تورينج . علاوة على ذلك ، يقول إن ه سؤال تجريبي مفتوح حول ما إذا كانت أي من هذه العمليات متورطة في عمل الدماغ البشر ي . هناك أيضًا بعض الأسئلة المفتوحة المهمة التي تغطي العلاقة بين أطروحة تشيرش - تورينغ والفيزياء ، و إمكانية الحوسبة المفرطة . عند تطبيق ها على الفيزياء ، ف إن الأطروحة ل ها عدة معانٍ محتملة : الكون يعادل آلة تورينج . و ب التالي ، ف إن حساب الوظائف غير العودية أمر مستحيل ماديًا . و قد أطلق على هذا اسم أطروحة تشيرش - تورينغ القوية ، أو مبدأ تشيرش - تورينج - دويتش ، و هو أساس للفيزياء الرقمية . الكون ليس يعادل آلة تورينج ( أي قوانين الفيزياء لا تورينج محسوب ) ، و لٰكن الأحداث المادية غير قابلة للإنضغاط . على سبيل المثال ، الكون الذي تتضمن في ه الفيزياء أعدادًا حقيقية عشوائية ، في مقابل الحقائق المحسوبة ، يقع ضمن هذه الفئة . الكون عبارة عن حاسوب فائق ، و من الممكن بناء أجهزة فيزيائية لتسخير هذه الخاصية و حساب الوظائف غير التكرارية . على سبيل المثال ، هناك سؤال مفتوح حول ما إذا كانت جميع الأحداث الميكانيكية الكمومية قابلة للحساب من نوع تورينج ، على الرغم من أن ه من المعروف أن النماذج الصارمة مثل آلات تورينج الكمومية تعادل آلات تورينج الحتمية . ( ليست ب الضرورة معادلة ب شكل فعال ؛ انظر أعلا ه . ) اقترح جون لوكاس وروجر بنروز أن العقل البشر ي قد يكون نتيجة لنوع من الحسابات « غير الخوارزمية » المحسنة ميكانيكيًا الكم . هناك العديد من الاحتمالات التقنية الأخرى التي تقع خارج أو بين هذه الفئات الثلاث ، و لٰكن ها تعمل على توضيح نطاق المفهوم . الجوانب الفلسفية للأطروحة ، فيما يتعلق ب كل من أجهزة الكمبيوتر الفيزيائية و البيولوجية ، تمت مناقشة ها أيضًا في كتاب أوديفريدي لعامحول نظرية العودية . وظائف غير قابلة للحساب يمكن للمرء أن يحدد رسميًا الوظائف غير القابلة للحساب . و من ال أمثلة المعروفة ل مثل هذه الوظيفة وظيفة بازي بيفر . تأخذ هذه الوظيفة مُدخلًا n وتُرجع أكبر عدد من الرموز يمكن لآلة تورينغ مع حالات n طباعت ها قبل التوقف ، عند التشغيل ب دون إدخال . إيجاد حد أعلى لوظيفة القندس المشغول يعادل حل مشكلة التوقف ، و هي مشكلة معروفة ب أن ها غير قابلة ل الحل ب واسطة آلات تورينج . نظرًا لأن وظيفة القندس المشغول لا يمكن حساب ها ب واسطة آلات تورينج ، تنص أطروحة تشيرش - تورينج على أن ه لا يمكن حساب هذه الوظيفة ب شكل فعال ب أي طريقة . تسمح العديد من النماذج الحسابية ب حساب وظائف ( تشيرش - تورينغ ) غير القابلة للحساب . تُعرف هذه بالحواسيب الفائقة . يجادل مارك بورجين ب أن الخوارزميات فائقة ال تكرار مثل آلات تورينج الاستقرائية تدحض أطروحة تشيرش - تورينج . تعتمد حجة ه على تعريف خوارزمية أوسع من التعريف العادي ، ل ذٰلك تسمى الوظائف غير القابلة للحساب التي تم الحصول علي ها من بعض آلات تورينج الاستقرائية ب أن ها قابلة للحساب . يختلف هذا التفسير لأطروحة تشيرش - تورينغ عن التفسير المقبول عمومًا في نظرية الحوسبة ، و الذي نوقش أعلا ه . الحجة القائلة ب أن الخوارزميات فائقة ال تكرار هي في الواقع خوارزميات ب معنى أطروحة تشيرش - تورينج لم تجد قبولًا واسعًا داخل مجتمع أبحاث الحوسبة . انظر أيضًا آلة مجردة نظرية الحوسبة نموذج الحوسبة كمال تورنغ روابط خارجية كتاب " The Church – Turing Th esis " . كتاب " Computation in Physical Systems " - A معالجة فلسفية شاملة للقضايا ذات الصلة . تم تخصيص عدد خاص ( المجلد العددمن مجلة نوتردام للمنطق الرسمي لأطروحة تشيرش - تورينغ . المراجع آلان تورنغ ال نظرية الحسابية فلسفة علم الحاسوب نظرية قابلية الحساب