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