أطروحة تشرش-تورينج
تؤكد أطروحة تشرش-تورينج أن كل دالة قابلة للحساب بواسطة أي إجراء فعال قابلة للحساب بواسطة آلة تورينج، مما يساوي الفكرة غير الرسمية للخوارزمية بنموذج رياضي دقيق.
Definition
أطروحة تشرش-تورينج هي الادعاء بأن الدوال القابلة للحساب بشكل حدسي هي بالضبط الدوال القابلة للحساب بواسطة آلة تورينج، أو ما يعادلها بواسطة حساب اللامدا (lambda calculus) أو الدوال التراجعية العامة؛ وهي أطروحة وليست مبرهنة لأن المفهوم الحدسي غير معرف رسميًا.
Scope
يغطي هذا الموضوع بيان الأطروحة، والأدلة المتقاربة من النماذج المقترحة بشكل مستقل، والتمييز بين الأطروحة الأصلية حول قابلية الحساب الفعالة والمتغيرات الفيزيائية أو النظرية المعقدة الأقوى، ودور الأطروحة كجسر بين الحدس والبرهان الرسمي في نظرية قابلية الحساب.
Core questions
- ماذا يعني تحديد المفهوم غير الرسمي للخوارزمية بنموذج رسمي؟
- لماذا يُعتبر تقارب النماذج المستقلة دليلاً قويًا على الأطروحة؟
- هل الأطروحة مبرهنة رياضية، تعريف، أم ادعاء تجريبي؟
- كيف تتجاوز الإصدارات الفيزيائية والنظرية المعقدة البيان الأصلي؟
Key theories
- تقارب نماذج الحساب
- تبين أن آلات تورينج، وحساب اللامدا لتشرش، والدوال التراجعية لجودل وهيربراند، تحدد نفس الفئة من الدوال بالضبط، وهذا الاتفاق المستقل هو الدليل الرئيسي المقدم للأطروحة.
- وضعها كأطروحة، وليست مبرهنة
- نظرًا لأن المفهوم الحدسي للإجراء الفعال غير مُصاغ رسميًا، لا يمكن إثبات الادعاء؛ يتم قبوله كتحديد أساسي يسمح للحجج الخوارزمية غير الرسمية أن تحل محل بناءات آلة تورينج الرسمية.
Clinical relevance
تسمح الأطروحة بالممارسة اليومية لوصف الخوارزميات بلغة شبه كود عالية المستوى بدلاً من آلات تورينج، حيث يُفترض أن أي مفهوم معقول للإجراء الفعال مكافئ لتورينج؛ كما أنها تؤطر النقاشات حول ما إذا كانت الأجهزة الفيزيائية أو الكمومية يمكنها في أي وقت الحساب بما يتجاوز ما هو قابل للحساب بواسطة تورينج.
History
في عام 1936، اقترح تشرش تحديد قابلية الحساب الفعالة بقابلية التعريف باللامدا (lambda-definability)، وجادل تورينج بشكل مستقل لنموذج آلته، وبعد ذلك أثبت تورينج وكليني وآخرون أن هذه الدوال والدوال التراجعية متكافئة. جودل، الذي كان متشككًا في البداية، اعتبر تحليل تورينج حاسمًا، وأصبح الادعاء المشترك معروفًا باسم أطروحة تشرش-تورينج.
Debates
- هل يمكن للحساب الفيزيائي أن يتجاوز حد تورينج؟
- تتعلق الأطروحة الأصلية بالإجراءات الفعالة، لكن الإصدارات الفيزيائية الأقوى تدعي أنه لا يوجد جهاز قابل للتحقيق فيزيائيًا يمكنه حساب دوال غير قابلة للحساب بواسطة تورينج. مقترحات الحوسبة الفائقة (hypercomputation) وتداعيات ميكانيكا الكم تبقي هذا الادعاء الموسع محل نزاع، حتى مع بقاء الأطروحة الكلاسيكية دون تحدي جوهري.
Key figures
- Alonzo Church
- Alan Turing
- Kurt Gödel
- Stephen Kleene
Related topics
Seminal works
- church1936
- turing1937
Frequently asked questions
- لماذا تسمى أطروحة بدلاً من مبرهنة؟
- إنها تربط نموذجًا رسميًا بالفكرة غير الرسمية للإجراء الفعال، وتلك الفكرة غير الرسمية ليس لها تعريف رياضي لإثبات الأشياء عنها. الدليل القوي هو أن كل محاولة مستقلة لإضفاء الطابع الرسمي على الحساب قد أسفرت عن نفس فئة الدوال، لكن هذا الدعم مفاهيمي وليس برهانًا.
- هل تنقض الحواسيب الكمومية أطروحة تشرش-تورينج؟
- لا. قد تحل الحواسيب الكمومية بعض المشكلات بشكل أسرع، لكنها تحسب نفس فئة الدوال تمامًا مثل آلات تورينج، لذا فإن الأطروحة الأصلية حول ما هو قابل للحساب لا تزال قائمة. إنها تتعلق بدلاً من ذلك بالإصدار الأقوى المتعلق بالتعقيد النظري الذي يهتم بالكفاءة بدلاً من قابلية الحساب.