التسلسل أو استمرار النجاح في نقي لامدا-حساب التفاضل والتكامل

Question

أنا أحاول حل التمرين التالي معين هنا.

النظر في ما يلي عدد التمثيل.كيفية تعريف إضافة ؟

|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

الخلف و السلف على مشغلي السهل أن تحدد:

Succ n = λx.n
Pred n = n (λx.x)

و "الواضح" الحل في تحديد ذلك هو استخدام خليفة العملية بالإضافة إلى اختبار صفر جنبا إلى جنب مع نقطة ثابتة combinator ، شيء من هذا القبيل (Y F) بالنسبة F أدناه (المشغل إذا و القيم المنطقية المحددة كالعادة):

F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

ولكن تحديد Is0 يبدو غير تافهة.المشكلة هي أن الأرقام |N| يستهلك N+1 الحجج ، و ن الحجج هي ببساطة مسح به.وبالتالي إن تطبيق مثل هذه الوظيفة ، فإنه يبدو من المعقول أن يتوقف تطبيقه عندما يصبح من الواضح أن الأرقام مثلاليس هوية.أعتقد أنه نوع من استمرار, ولكن لا أستطيع أن أتخيل كيف أن نموذج في نقي لامدا-حساب التفاضل والتكامل.ربما شخص يعرف أي النصائح التي قد تساعد ؟

وهو تسلسل المشغل يمكن أن يساعد أيضا على تحديد ذلك.إذا طلب أحد الأرقام |m| تأخر حتى الأرقام |n| يتم تطبيق كل الحجج ، فإن النتيجة ستكون بالضبط الأرقام |n+m|.ربما يوجد البديل من هذا التسلسل combinator في نقي لامدا-حساب التفاضل والتكامل ؟

الإجابة التي يتم توفيرها من قبل صاحب التمرين يستخدم غير نقية العملية (أي ، IsProcedure والذي يتحقق ما إذا كانت الحجة هي الدالة).

محدث: فإنه ليس من الصعب أن تفعل النيابة العامة في لامدا-حساب التفاضل والتكامل (تفاصيل CBV يمكن العثور عليها هنا).يبدو أن هذا لا يكفي لحل المشكلة.

محدث:إذا كان لدينا نسخة من اقتباس-eval وظائف نقية لامدا-حساب التفاضل والتكامل ، ثم يجب أن يكون هناك وظيفة $eq$, التي تعترف إذا نقلت امدا التعبيرات نحويا على قدم المساواة ، و يمكننا بناء Is0 باستخدام $eq$.ولكن أشك في أن $eq$ هو يمكن تحديدها.والسبب هو "genericity يما" (Barendregt الكتاب ، يما 14.3.24).إذا كنا قادرين على اختبار المساواة على ما نقلت لامدا-الشروط ثم ($eq$ (اقتباس $\Omega$) (اقتباس $\lambda x.x$)) سيعود $False$, و genericity يعني أن ($eq$ (اقتباس $\lambda x.x$) (اقتباس $\lambda x.x$)) أيضا عودة $False$.هل هذا يتعارض مع إمكانية بناء اقتباس في نقي لامدا-حساب التفاضل والتكامل ؟

Answer 1

أنا لا أعتقد أنك سوف تجد ما كنت تبحث عنه في نقي امدا حساب التفاضل والتكامل.المفتاح هو هذا البيان قمت بها:

وهو تسلسل المشغل يمكن أن يساعد أيضا على تحديد ذلك.إذا طلب أحد الأرقام |م| تأخر حتى الرقم |n| يتم تطبيقها على جميع الحجج ، ...

حسنا, نماذج امدا حساب التفاضل والتكامل هي من المفترض أن تكون مثل:

$$U \كونغ U^U$$

النقطة هذا هو أن كل الدلالات القيمة $u \في U$ يمكن تطبيقها على شيء.لذلك لا معنى للحديث عن شيء يجري "على جميع الحجج." لا يوجد أي القيمة التي لا يمكن تطبيقها على أكثر الحجج الطاهرة امدا حساب التفاضل والتكامل.

أنا لا أعرف من ناحية نموذج/حجة أن هذا تمثيل المواد الطبيعية يجعل من المستحيل تنفيذ IsZero, على الرغم من أن بعض التفكير يجعله يبدو غير مرجح.ومع ذلك ، إذا كان من الممكن في نقي امدا حساب التفاضل والتكامل ، وسوف تضطر إلى معنى لغويا و لا يكون على أساس المفاهيم التي هي فقط النحوية.

تحرير:هنا رسم حجة.تعريف $\mathsf{IsZero}$ يجب في نهاية المطاف الحد من مثل:

$$\mathsf{IsZero}\ n ightsquigarrow^* n \overrightarrow v$$

والسبب هو أن تطبيق بعض عدد من القيم هو الآلية الوحيدة في امدا حساب التفاضل والتكامل في الواقع التمييز بين الأرقام.فإنه يحتاج إلى أن يكون حال: $$0 \overrightarrow v = \mathsf{صحيح} \\ \mathsf{s}n \overrightarrow v = \mathsf{كاذبة}$$ ومع ذلك, كل $\overrightarrow v$ هذا هو حال: $$||\overrightarrow v| + k|\overrightarrow v = k ||$$ (حيث $|\overrightarrow v|$ هو طول $\overrightarrow v$).ولكن فقط $|1| = \mathsf{كاذبة}$ (إذا كان هذا هو اتفاقية المختار).في اللغة الإنجليزية هناك لا بد على عدد من الشروط المطلوبة للحصول على منطقية من خلال تطبيق الأرقام.لذلك لا يمكن أن تكون هناك $\overrightarrow v$ الذي يرضي المعادلات لجميع الأرقام ، وبالتالي $\mathsf{IsZero}$ لا يمكن تعريفها.

Answer 2

الطريقة الأكثر مباشرة إلى تحديد ذلك في لامدا-حساب التفاضل والتكامل هو علاج الأرقام كما لو كانت القوائم المرتبطة ، catenate القوائم.للقيام بذلك الحق ، فمن الضروري استخدام إضافية المتغيرات استبدال المتغيرات الخارجية من كل عدد مما التعبير عن الرقم الثاني يمكن أن تكون بديلا الداخلية متغير الناتج التعبير عن الرقم الأول.هذا ينتج التعبير التالي الإضافة:

  λw.λx.λy.λz.w y (x y z)