الدوال التراجعية وآلات السجل
تبني نظرية الدوال التراجعية الدوال القابلة للحساب من عدد قليل من العمليات الأساسية، بينما تحسب آلات السجل بالأعداد الصحيحة المخزنة في السجلات، وهما نموذجان يحيطان بآلة تورينج ويؤكدان متانة قابلية الحساب.
Definition
الدوال التراجعية العامة هي تلك التي تُبنى من الثوابت، والتالي، والإسقاطات عن طريق التركيب، والتراجعية البدائية، والتصغير غير المحدود؛ آلات السجل هي أجهزة مجردة تحسب عن طريق زيادة، ونقصان، واختبار محتويات مجموعة محدودة من السجلات التي تحتوي على أعداد طبيعية.
Scope
يغطي هذا الموضوع الدوال التراجعية البدائية، وإضافة التصغير غير المحدود للحصول على الدوال التراجعية العامة، ودالة أكرمان كدالة قابلة للحساب وليست تراجعية بدائية، وآلات السجل والعدادات وعالميتها، وتكافؤ كل هذه النماذج مع قابلية تورينج للحساب.
Core questions
- كيف يمكن تعريف الدوال القابلة للحساب حسابيًا دون أي آلة؟
- لماذا يُعد التصغير غير المحدود ضروريًا بما يتجاوز التراجعية البدائية؟
- كيف تحقق آلات السجل البسيطة القوة الكاملة للحساب؟
- لماذا تتطابق هذه النماذج الحسابية والآلية مع آلات تورينج؟
Key theories
- التكافؤ مع قابلية تورينج للحساب
- الدوال التراجعية العامة والدوال التي تحسبها آلات السجل هي بالضبط الدوال القابلة للحساب بواسطة تورينج، مما يعزز أطروحة تشرش-تورينج من خلال نماذج معرفة بمصطلحات حسابية بحتة وآلية أولية.
- ما وراء التراجعية البدائية
- دالة أكرمان كلية وقابلة للحساب ومع ذلك تنمو بسرعة كبيرة بحيث لا تكون تراجعية بدائية، مما يدل على أن البحث غير المحدود ضروري وأن الدوال التراجعية البدائية هي فئة فرعية مناسبة من الدوال القابلة للحساب.
- عالمية آلات السجل
- أظهر مينسكي أن آلة تحتوي على عدادين فقط وعمليات الزيادة، والنقصان، واختبار الصفر هي بالفعل كاملة تورينج، وهو دليل صارخ على مدى قلة الهيكل الذي يتطلبه الحساب الكامل.
Clinical relevance
تُنمذج آلات السجل الحساب العددي للمعالجات الحقيقية بشكل مباشر أكثر مما تفعله الأشرطة، وتتوافق التراجعية البدائية مع البرامج التي تنتهي دائمًا وتُشكل أساس اللغات الوظيفية الكلية وتحليل الإنهاء، وتربط وجهة نظر الدالة التراجعية الحساب بأسس الرياضيات.
History
عرّف غودل وهربراند الدوال التراجعية العامة في أوائل ثلاثينيات القرن الماضي، وطوّر كليني النظرية، بما في ذلك دور التصغير. كان أكرمان قد عرض في وقت سابق دالته سريعة النمو، وقدم مينسكي آلات السجل والعدادات في الستينيات، وأثبت أن آلات العدادات ذات العدادين عالمية.
Key figures
- Kurt Gödel
- Stephen Kleene
- Wilhelm Ackermann
- Marvin Minsky
Related topics
Seminal works
- cutland1980
- minsky1967
Frequently asked questions
- ما الفرق بين الدوال التراجعية البدائية والدوال التراجعية العامة؟
- تُبنى الدوال التراجعية البدائية باستخدام حلقات محدودة وتنتهي دائمًا، لكنها لا تشمل كل دالة قابلة للحساب. إضافة التصغير غير المحدود، وهو بحث قد يستمر إلى أجل غير مسمى، ينتج عنه الدوال التراجعية العامة، التي تتطابق تمامًا مع الدوال القابلة للحساب بواسطة تورينج.
- كيف يمكن لآلة ذات عدادين فقط أن تكون قوية مثل الحاسوب؟
- أظهر مينسكي أن سجلين يحملان أعدادًا طبيعية، مع عمليات الزيادة، والنقصان، واختبار الصفر فقط، يمكنهما محاكاة آلة تورينج عن طريق ترميز شريطها في السجلات. البناء غير فعال للغاية، لكنه يثبت أن الحد الأدنى من الأجهزة يصل بالفعل إلى القوة الكاملة للحساب.