أطروحة تشرش-تورينغ

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

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

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

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

بيان تشيرش وتورنج

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

† سنستخدم تعبير «وظيفة قابلة للحساب» للإشارة إلى دالة يمكن حسابها بواسطة آلة، وندع «قابلة للحساب بشكل فعال» تشير إلى الفكرة البديهية دون تحديد محدد مع أي من هذه التعريفات.[9]

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

قيل ... أن «دالة قابلة للحساب بشكل فعال إذا كان من الممكن العثور على قيمها من خلال عملية ميكانيكية بحتة». قد نأخذ هذا حرفياً، ونفهم أنه من خلال عملية ميكانيكية بحتة، يمكن تنفيذها بواسطة آلة. التطور ... يؤدي إلي ... لتحديد الحاسوبية † مع الحسابية فعالة. [ † هي الحاشية المقتبسة أعلاه. ]

التاريخ

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

فترة 1930-1952

في سياق دراسة المشكلة، قدم تشرش وتلميذه ستيفن كلاين مفهوم الوظائف القابلة للتحديد، وتمكنا من إثبات أن العديد من الفئات الكبيرة من الوظائف التي يتم مواجهتها بشكل متكرر في نظرية الأعداد كانت قابلة للتحديد λ.[14] بدأ النقاش عندما اقترحت تشيرش على جودل أن على المرء أن يعرف الوظائف «القابلة للحساب بشكل فعال» كوظائف قابلة للتحديد λ. ومع ذلك، لم يكن جودل مقتنعًا ووصف الاقتراح بأنه «غير مرض تمامًا».[15] بدلاً من ذلك، في المراسلات مع تشيرش (حوالي 1934-1935)، اقترح جودل إضفاء البديهية على مفهوم «الحساب الفعال». في الواقع، في رسالة أرسلها تشرش عام 1935 إلى كلاين، أفاد تشرش بأن:

لكن جودل لم يقدم أي إرشادات أخرى. في النهاية، كان يقترح تكراره، بعد تعديله من خلال اقتراح هيربراند، الذي ذكره جودل بالتفصيل في محاضراته عام 1934 في برينستون نيوجيرسي (قام كلاين وروسر بنسخ الملاحظات). لكنه لم يعتقد أنه يمكن تحديد الفكرتين بشكل مرضٍ «إلا بطريقة الكشف عن مجريات الأمور».[16]

بعد ذلك، كان من الضروري تحديد وإثبات تكافؤ مفهومين للقدرة على الحساب الفعال. مُجهزًا بحساب التفاضل والتكامل λ والعودة «العامة»، قدم ستيفن كلاين بمساعدة تشرش وجي باركلي روسر البراهين (1933، 1935) لإثبات أن الحسابين متكافئان. قام تشرش بعد ذلك بتعديل أساليبه لتشمل استخدام عودية هيربراند-جودل ثم أثبت (1936) أن مسألة القرار غير قابل للحل: لا توجد خوارزمية يمكنها تحديد ما إذا كانت الصيغة جيدة التكوين.[17]

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

يضيف تورينج تعريفًا آخر، يساوي روسر الثلاثة: في غضون وقت قصير فقط، ظهرت ورقة تورينج 1936-1937 «حول الأرقام المحسوبة، مع تطبيق على مشكلة مسألة القرار».[20] ذكر فيه فكرة أخرى عن «الحوسبة الفعالة» مع إدخال آلاته (المعروفة الآن باسم النموذج الحسابي المجرد لآلة تورينج). وفي رسم إثبات تمت إضافته باعتباره «ملحقًا» إلى ورقته البحثية 1936-1937، أظهر تورينج أن فئات الوظائف المحددة بواسطة حساب التفاضل والتكامل λ وآلات تورينج تتطابق.[25] كان تشرش سريعًا في إدراك مدى جاذبية تحليل تورينج. في مراجعته لورقة تورينج أوضح أن فكرة تورينج جعلت «التماثل بفعالية في المعنى العادي (غير المحدد صراحة) واضحًا على الفور».[26] في غضون بضع سنوات (1939) سيقترح تورينج، مثل تشرش وكلين من قبله، أن تعريفه الرسمي لعامل الحوسبة الميكانيكية هو التعريف الصحيح.[27] وهكذا، بحلول عام 1939، اقترحت كل من تشيرش (1934) وتورنج (1939) بشكل فردي أن «الأنظمة الرسمية» يجب أن تكون تعريفات «للحساب الفعال».[28][29]

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

التطورات اللاحقة

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

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

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

الأطروحة كتعريف

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

نجاح الرسالة

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

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

الاستخدام غير الرسمي في البراهين

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

الاختلافات

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

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

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

المضامين الفلسفية

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

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

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

وظائف غير قابلة للحساب

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

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

انظر أيضًا

روابط خارجية

  • كتاب "The Church–Turing Thesis".
  • كتاب "Computation in Physical Systems" -A معالجة فلسفية شاملة للقضايا ذات الصلة.
  • Kaznatcheev، Artem (11 سبتمبر 2014). "Transcendental idealism and Posts variant of the Church-Turing thesis". Journal of Symbolic Logic. ج. 1 ع. 3: 103–105. مؤرشف من الأصل في 2023-09-14.
  • تم تخصيص عدد خاص (المجلد 28، العدد 4، 1987) من مجلة نوتردام للمنطق الرسمي لأطروحة تشيرش - تورينغ.

المراجع

  1. ^ "معلومات عن أطروحة تشرش-تورينغ على موقع treccani.it". treccani.it. مؤرشف من الأصل في 2020-08-15.
  2. ^ "معلومات عن أطروحة تشرش-تورينغ على موقع catalogue.bnf.fr". catalogue.bnf.fr. مؤرشف من الأصل في 2019-05-01.
  3. ^ "معلومات عن أطروحة تشرش-تورينغ على موقع jstor.org". jstor.org. مؤرشف من الأصل في 2020-05-26.
  4. ^ Robert Soare, "Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory" نسخة محفوظة 14 أغسطس 2021 على موقع واي باك مشين.
  5. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع TuringLearn
  6. ^ Church 1936
  7. ^ Kleene 1936
  8. ^ Turing 1937a
  9. ^ Turing، A.M. (1938). Systems of Logic Based on Ordinals (PDF) (PhD). Princeton University. ص. 8. مؤرشف من الأصل (PDF) في 2012-10-23. اطلع عليه بتاريخ 2012-06-23.
  10. ^ Gandy (1980) states it this way: What is effectively calculable is computable. He calls this "Churchs Thesis".
  11. ^ David Hilbert and Wilhelm Ackermann: Grundzüge der theoretischen Logik, Berlin, Germany, Springer, 1st ed. 1928. (6th ed. 1972, (ردمك 3-540-05843-5)) English Translation: David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic, AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950
  12. ^ Daviss commentary before Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:88. Church uses the words "effective calculability" on page 100ff.
  13. ^ In his review of Churchs Thesis after 70 Years edited by Adam Olszewski et al. 2006, Peter Smiths criticism of a paper by Muraswski and Wolenski suggests 4 "lines" re the status of the Church–Turing Thesis: (1) empirical hypothesis (2) axiom or theorem, (3) definition, (4) explication. But Smith opines that (4) is indistinguishable from (3), cf Smith (July 11, 2007) Churchs Thesis after 70 Years at http://www.logicmatters.net/resources/pdfs/CTT.pdf نسخة محفوظة 2021-08-13 على موقع واي باك مشين.
  14. ^ cf footnote 3 in Church 1936a An Unsolvable Problem of Elementary Number Theory in Davis 1965.
  15. ^ Dawson 1997.
  16. ^ Sieg 1997:160 quoting from the 1935 letter written by Church to Kleene, cf Footnote 3 in Gödel 1934 in Davis 1965.
  17. ^ cf. Church 1936 in Davis 1965.
  18. ^ Daviss commentary before Gödel 1934 in Davis 1965.
  19. ^ For a detailed discussion of Gödels adoption of Turings machines as models of computation, see Shagrir. "Goedel on Turing on Computability" (PDF). مؤرشف من الأصل (PDF) في 2015-12-17. اطلع عليه بتاريخ 2016-02-08.[التاريخ مفقود]
  20. ^ ا ب Turing 1937.
  21. ^ cf. Editors footnote to Post 1936 Finite Combinatory Process. Formulation I. at Davis 1965.
  22. ^ Post 1936 in Davis 1952:291.
  23. ^ Sieg 1997:171 and 176–177.
  24. ^ Sieg 1997:160.
  25. ^ Turing 1936–37 in Davis 1965.
  26. ^ Church 1937.
  27. ^ Turing 1939 in Davis:160.
  28. ^ cf. Church 1934 in Davis 1965, also Turing 1939 in Davis 1965.
  29. ^ Kleene 1943 in Davis 1965. footnotes omitted.
  30. ^ Kleene 1952
  31. ^ ا ب Gandy 1980.
  32. ^ Gandy 1980
  33. ^ Sieg 1998–9 in Sieg, Somner & Talcott 2002:390ff; also Sieg 1997:154ff.
  34. ^ A collection of papers can be found in Olszewski, Woleński & Janusz (2006). Also a review of this collection: Smith، Peter (11 يوليو 2007). "Churchs Thesis after 70 Years" (PDF). مؤرشف من الأصل (PDF) في 2021-08-13.
  35. ^ See also Hodges، Andrew (2005). "Did Church and Turing Have a Thesis about Machines?" (PDF). مؤرشف من الأصل (PDF) في 2016-03-04. اطلع عليه بتاريخ 2014-07-27.
  36. ^ Gödel، Kurt (1995) [193?]. "Undecidable Diophantine Propositions". في Feferman (المحرر). Collected Works. New York: Oxford University Press. ج. 3. ص. 168. ISBN:978-0-19-507255-6. OCLC:928791907. {{استشهاد بكتاب}}: الوسيط غير المعروف |بواسطة= تم تجاهله يقترح استخدام |عبر= (مساعدة)
  37. ^ Soare، Robert I. (سبتمبر 1996). "Computability and Recursion". Bulletin of Symbolic Logic. ج. 2 ع. 3: 284–321. DOI:10.2307/420992. JSTOR:420992.
  38. ^ Kleene 1952:320
  39. ^ Gurevich 1988:2
  40. ^ Horsten in Olszewski 2006:256.
  41. ^ Gabbay 2001:284
  42. ^ Piccinini، Gualtiero (يناير 2007). "Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy" (PDF). Synthese. ج. 154 ع. 1: 97–120. DOI:10.1007/s11229-005-0194-z. مؤرشف من الأصل (PDF) في 2021-03-07.
  43. ^ Arora، Sanjeev؛ Barak، Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN:978-0-521-42426-4. مؤرشف من الأصل في 2024-03-07. Sections 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9".
  44. ^ "Official Problem Description" (PDF). مؤرشف من الأصل (PDF) في 2005-11-24.
  45. ^ Kaye، Phillip؛ Laflamme، Raymond؛ Mosca، Michele (2007). An introduction to quantum computing. Oxford University Press. ص. 5–6. ISBN:978-0-19-857049-3.
  46. ^ van Emde Boas، Peter (1990). "Machine Models and Simulations". Handbook of Theoretical Computer Science A. Elsevier. ص. 5.
  47. ^ Kaye، Phillip؛ Laflamme، Raymond؛ Mosca، Michele (2007). An introduction to quantum computing. Oxford University Press. ص. 5–6. ISBN:978-0-19-857049-3.Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2007). An introduction to quantum computing. Oxford University Press. pp. 5–6. ISBN 978-0-19-857049-3.
  48. ^ Eberbach & Wegner 2003.
  49. ^ Abramson، Darren (2011). "Philosophy of mind is (in part) philosophy of computer science". Minds and Machines. ج. 21 ع. 2: 203–219. DOI:10.1007/s11023-011-9236-0. مؤرشف من الأصل في 2021-08-14.
  50. ^ For a good place to encounter original papers see Chalmers، المحرر (2002). Philosophy of Mind: Classical and Contemporary Readings. New York: Oxford University Press. ISBN:978-0-19-514581-6. OCLC:610918145.
  51. ^ Copeland، B. Jack (2004). "Computation". في Floridi (المحرر). The Blackwell guide to the philosophy of computing and information. Wiley-Blackwell. ص. 15. ISBN:978-0-631-22919-3.
  52. ^ cf Penrose، Roger (1990). "Algorithms and Turing machines". The Emperors New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford: Oxford University Press. ص. 47–49. ISBN:978-0-19-851973-7. OCLC:456785846.
  53. ^ Also the description of "the non-algorithmic nature of mathematical insight", Penrose، Roger (1990). "Where lies the physics of mind?". The Emperors New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford: Oxford University Press. ص. 416–418. ISBN:978-0-19-851973-7. OCLC:456785846.
  54. ^ Piergiorgio Odifreddi (1989). Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics. Amsterdam: North Holland. ج. 125.
  55. ^ Burgin، Mark (2005). Super-Recursive Algorithms. Monographs in Computer Science. New York: Springer. ISBN:978-0-387-95569-8. OCLC:990755791.