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