Lambda Calculus دون متغيرات مجانية قوية مثل حساب التفاضل والتكامل Lambda؟

Question

السؤال الأول: كيف يثبت المرء أنه من خلال إزالة المتغيرات المجانية (غير المنفغة) من حساب التفاضل والتكامل Lambda، والسماح للمتغيرات المنضم فقط، فإن قوتها لا تقلل (لا تزال تورينج كاملة)؟

السؤال الثاني: هو الاقتراح المذكور أعلاه صحيح حقا؟هل Lambda Calculus Sans متغيرات مجانية تورينج حقا؟

Answer 1

أنا أفترض أنك تشير إلى حساب التفاضل والتكامل Lambda غير المصمم.

إذا كان الأمر كذلك، اكتب $ \ newcommand {\ num} [1] {\ ulcorner # 1 \ urcorner} \ Num {n} $ لأرقام الكنيسة الاكتبرة الطبيعية $ n $ .

من المعروف أنه يوجد مصطلح مغلق (أي متغيرات مجانية) $ TM $ مثل ذلك $$ TM \ \ Num {I} \ \ Num {n} \= _ {\ beta \ eta} \ \ Num {m} $ إذا، وفقط إذا، $ i $ آلة Turingth (في بعض التعداد القياسي) تشغيل مع إدخال $ n \ في \ mathbb n $ (مشفرة كالمعتاد) توقف إرجاع $ m $ كإخراج.

في الواقع، الكتابة $ tm $ تمرين قياسي "البرمجة" في حساب التفاضل والتكامل Lambda. لذلك، يمكن للمرء أن يمثل الشريط كزوج أزواج أو أزواج من ... (AKA قائمة سلبيات) من الرموز. ثم "يخطو" الروتين الفرعي لتحسين الشريط ويمكن كتابة حالة TM. أخيرا، يتم الاحتجاج بالخطوة الفرعية للخطوة حتى يتم الوصول إلى حالة وقف. يمكن تحقيق هذه الخطوة الأخيرة باستخدام منفذ ثابت نقطة مثل $ y $ .

لأنه يمكننا محاكاة أي آلة تورينج، ونحن نحصل على اكتمال.

---

دليل بديل، وهو (في رأيي) أسهل في تنفيذ التفاصيل الكاملة: أثبت أن أي وظيفة متكررة عامة يمكن أن تكون $ \ Lambda $ -Defined باستخدام مصطلح لامدا مغلق. لذلك، المضي قدما في التعريفي على تعريف الوظيفة العامة العودية.

في الواقع، حتى لو كنت لا تهدف بشروط مغلقة، في عملية البرمجة هذه، ستحصل على واحدة مغلقة بطريقة طبيعية. بعد كل شيء، عندما لا يحتاج البرمجة إلى متغير لم يتم الإعلان عنه مسبقا.

نظرا لأن الوظائف العودية العامة هي بالضبط تلك التي يمكن حسابها بواسطة آلة تورينج، نحصل على اكتمال حساب التفاضل والتكامل Lambda المغلق.