مرجع
آخر الزيارات

تطابق كاري-هوارد

3٬675 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في نظرية لغات البرمجة ونظرية البرهان، تطابق كاري-هوارد هي العلاقة المباشرة بين البرامج والبراهين الراضية. تجد هنا «α → (β → α) و»، «الإسقاطات: و» و«الصياغة العامة» ضمن 30 قسماً.
المحتويات
  1. α → (β → α) و
  2. الإسقاطات: و
  3. الصياغة العامة
  4. تطبيقات أخرى
  5. ككائن
  6. ,
  7. ————————————————————————————————————
  8. المراجع الأساسية
  9. الأصل والنطاق والنتائج
  10. مطابقة كاري-هاوارد-لامبك
  11. التفسيرات الفلسفية
  12. تفسير بروير-هايتينغ-كولموغوروف
  13. تعميمات
  14. refs
  15. ,
  16. الإمكانية في منطق موجهات وأنواع الموناد للتأثيرات
  17. أمثلة
  18. الأنظمة المتوافقة
  19. ————————————————————————————————————
  20. المنطق الكلاسيكي وموصلات التحكم
  21. الأوراق الاصطناعية
  22. كتب
  23. دور دي بروين
  24. قراءة إضافية
  25. التحقيق القابل للتنفيذ
  26. ,
  27. ————————————————————————————————————————
  28. تطابق كوري-هوارد في هاسكل
  29. ,
  30. حساب المتتاليات

قبل الخوض في التفاصيل، في نظرية لغات البرمجة ونظرية البرهان، تطابق كاري-هوارد هي العلاقة المباشرة بين البرامج والبراهين الراضية. تُعرف كذلك باسم تماثل كاري-هوارد أو المعادلة, أو البرهانات كبرامج والمقترحات- أو الصيغ كأنواع تفسير. وفيما يلي تفاصيل أوسع عن ذلك.

إضافةً إلى ذلك، هي تعميم للتمثيل الصرفي للتمثيل بين أنظمة المنطق الرسمي وحسابات الحوسبة التي اكتشفها لأول مرة عالم الرياضيات الأمريكي هاسكل كاري والمنطقي ويليام آلفين هوارد. هي الرابط بين المنطق والحوسبة الذي يُنسب عادة إلى كاري وهوارد، على الرغم من أن الفكرة تتعلق بالتفسير التشغيلي للمنطق الحسي الذي قدمه لويتسن براور، وأندريه كولموغوروف وستيفن كول كلين (انظر ). تم توسيع العلاقة لتشمل نظرية الفئات كـمراسلة كاري-هوارد-لامبك.

α → (β → α) و

من جهة ثانية، بعد أن أشار هاسكل كاري إلى المطابقة الصرفية بين الاستدلال الحدسي على طراز هيلبرت والمنطق التركيبي الموصوف بالأنواع، أوضح ويليام آلفين هوارد في سنة 1969 تشابهًا صرفيًا بين البرامج في تكامل لامدا الموصوف بالأنواع والأدلة في الاستدلال الطبيعي. أدناه، يُعرض الجانب الأيسر بشكل رسمي للاستدلال الطبيعي الحدسي للفرضيات كحساب للسلسلات (يعد استخدام السلسلات أمرًا شائعًا في مناقشات التناظر بين كاري وهوارد حيث يسمح لقاعدة الاستدلال أن تُصرح بشكل أنظف)، والجانب الأيمن يُظهر قواعد التخصيص في تكامل لامدا. في الجانب الأيسر، تشير Γ، Γ1 وΓ2 إلى تسلسلات مرتبة من الصيغ بينما في الجانب الأيمن، تشير إلى تسلسلات من الصيغ المسماة (أي المخصصة بالأنواع) مع جميع الأسماء مختلفة.

(α → (β → γ)) → ((α → β) → (α → γ)).

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

  • المنطق من الدرجة الأعلى ونظام Fω لجيرارد.
  • الأنواع الاستقرائية كالنوع البياني الجبري.
  • الضرورة في منطق موجهات وحساب المراحل

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

الاستدلال الطبيعي الحدسي و تكامل لامدا الموصوف بالأنواع

وفي هذا السياق، نظام F لجيرارد-رينولد كلغة مشتركة لكل من منطق المقترحات من الدرجة الثانية وتكامل لامدا الموصوف بالأنواع البوليموريك.

وفي هذا الصدد، لإعادة صياغة المطابقة، فإن إثبات Γ ⊢ α يعني امتلاك برنامج يقوم، عند إعطائه قيمًا بالأنواع المدرجة في Γ، بإنشاء كائن من النوع α. يتوافق الافتراض/الفرضية مع إدخال متغير جديد بنوع جديد غير مقيد، وقاعدة تتوافق مع تجريد الدالة وقاعدة تتوافق مع تطبيق الدالة. لاحظ أن المطابقة ليست دقيقة إذا تم أخذ السياق Γ كمجموعة من الصيغ، حيث مثلًا، لن يتم التمييز بين مصطلحات λ-التي هي λx.λy.x و λx.λy.y من النوع في المطابقة. يتم إعطاء الأمثلة أدناه.

الإسقاطات: و

التكرير: إذا كان مورفزم، فإن هو مورفزم.

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

التقييم:

  • الهوية:
  • التكوين:
  • النوع الوحيد (الكائن النهائي):
  • المنتج الكارتيسي:
  • الإسقاطات اليسرى واليمنى:
  • التكرير (تقنية في البرمجة الوظيفية):
  • التطبيق:
  • أخيرًا، المعادلات في الفئة هي:
  • (إذا كانت المصطلحات مصنفة بشكل جيد)
  • تستنتج هذه المعادلات القوانين التالية:
  • الآن، يوجد بحيث إذا وفقط إذا كانت قابلة للإثبات في المنطق الحدسي الاستنباطي.

الصياغة العامة

يتم تلخيص ذلك في الجدول التالي:

علاوةً على ذلك، بين نظام الاستدلال الطبيعي وحساب لامدا، توجد المطابقات التالية:

وعلى صعيد آخر، على مستوى أنظمة البرهان ونماذج الحسابات، تُظهر المطابقة بشكل رئيسي تطابق الهيكل، أولاً، بين بعض الصيغ المحددة للأنظمة المعروفة بنظام الاستدلال على الطراز هيلبرت و المنطق التركيبي، وثانياً، بين بعض الصيغ المحددة للأنظمة المعروفة بالاستدلال الطبيعي و تكامل لامدا.

من جانب آخر، إذا كان التكميل يأتي في شكلين، فذلك لأنه توجد طريقتان للتفكير في مراسلة كاري-هوارد. إذا اعتبر المرء أن كل خطوة برهان يجب أن تكون حسابية، فإن التكميل الكوني يُفسر كمنتج معتمد والتكميل الوجودي كـمجموع معتمد (وهذا يتوافق مع تفسير البرهان كعنصر مُعين في طريقة تشرتش). إذا اعتُبر العكس، حيث يمكن تجاهل بعض الخطوات الحسابية التافهة، فيتم تفسير التكميل الكوني كـنظام الأنواع معتمد والتكميل الوجودي كنظام الأنواع معتمد (وهذا يتوافق مع تفسير البرهان كعنصر مُعين في طريقة كاري، التي كانت فعلاً النهج الذي اتبعه هوارد).

وفي هذا الصدد، على مستوى الصيغ والأنواع، تقول المراسلة أن التضمين يتصرف مثل نوع دالة، والتقاطع مثل نوع "المنتج" (يمكن تسمية هذا بالـtuple أو الـstruct أو الـlist أو مصطلح آخر حسب اللغة)، والتفاضل مثل نوع المجموع (يمكن تسمية هذا النوع بالاتحاد)، والصيغة الكاذبة مثل النوع الفارغ والصيغة الصحيحة مثل نوع الوحدة (الذي يتضمن العضو الوحيد هو الكائن الفارغ). تتوافق الكميات مع المساحة الوظيفية المعتمدة أو المنتجات (حسب المناسب).

ومن جهة أخرى، في صياغتها الأكثر عمومية، تعد مراسلة كاري-هوارد مراسلة بين أنظمة البرهان الرسمية ونظام الأنواع لـنموذج حوسبة. على وجه الخصوص، تنقسم إلى مراسلتين. واحدة على مستوى صيغة جيدة التكوين ونوع بيانات الذي لا يعتمد على أي نظام برهان أو نموذج حوسبة معين يتم اعتباره، وأخرى على مستوى البراهين الرياضية والبرامج التي تكون هذه المرة محددة بالاختيار الخاص لنظام البرهان ونموذج الحوسبة المعتمد.

تطبيقات أخرى

وعلى صعيد آخر، تعتمد هذه الطريقة على فهرسة مجموعات الأنماط الجينية (وهي أشجار البرامج التي يُنتجها نظام البرمجة الوراثية) بحسب إثباتها المماثل في تناظر كوري–هوارد (والذي يُشار إليه هنا بـ «النوع» أو «النوع التطوري»).

في هذا الإطار، مؤخرًا، اقتُرح استخدام هذا التناظر كطريقة لتعريف تقسيم فضاء البحث في برمجة وراثية.

من جهة ثانية، فإن تناظر كوري–هوارد يشكّل حجة ضد قابلية براءات الاختراع في البرمجيات: بما أن الخوارزميات ما هي إلا إثباتات رياضية، فإن إتاحة تسجيل براءة اختراع على الخوارزميات يعني ضمنًا إتاحة تسجيل براءة اختراع على الإثباتات الرياضية. وهذا يعني أن النظرية قد تُصبح ملكية خاصة؛ وسيضطر الرياضي إلى الدفع لاستخدامها، والاعتماد على الشركة التي تبيعها دون الكشف عن الإثبات، بينما تُخلي مسؤوليتها عن أي أخطاء.

علاوةً على ذلك، كما أشار مدير الأبحاث في المعهد الفرنسي للأبحاث في علوم الحاسب الآلي والأتمتة برنار لانغ،

ككائن

  • إذا كانت و كائنات، فإن و كائنات.
  • المورفزمات (الاستدلالات/المصطلحات) تشمل:
  • الهويات:
  • التكوين: إذا كان و مورفزمات، فإن هو مورفزم
  • المورفزمات النهائية:
  • المنتجات: إذا كان و مورفزمات، فإن هو مورفزم

,

علاوةً على ذلك، الإثبات العادي لـ (β → α) → (γ → β) → γ → α في الاستنتاج الطبيعي كما يُرى كـ λ-تعبير

في هذا الإطار، ——————————————————————————————————— ————————————————————————————————————————————————————————————————————

  • a:β → α, b:γ → β, g:γ ⊢ a : β → α
  • a:β → α, b:γ → β, g:γ ⊢ b g : β
  • ————————————————————————————————————————————————————————————————————————
  • a:β → α, b:γ → β, g:γ ⊢ a (b g) : α

من جهة ثانية، يعرض المخطط أدناه إثباتًا للصيغة في نظام الاستنتاج الطبيعي، ويوضح كيف يمكن تفسير هذا الإثبات باعتباره تعبير لامبدا من النوع .

a:β → α, b:γ → β, g:γ ⊢ b : γ → β

a:β → α, b:γ → β, g:γ ⊢ g : γ

  • نضع , , و، لينتج:
  • ثم نفصل النتيجة:
  • هذه هي الصيغة المقابلة لنوع (S (K S)). حالة خاصة من هذه النظرية تكون عندما :

————————————————————————————————————

⊢ λ a. λ b. λ g. a (b g) : (β → α) → (γ → β) → γ → α

المراجع الأساسية

.

كذلك، دي بروين، نيكولاس (1968)، أوتومات، لغة للرياضيات، قسم الرياضيات، جامعة آيندهوفن للتكنولوجيا، تقرير TH-68-WSK-05. أعيد نشره بصيغة منقحة، مع تعليق من صفحتين، في: الأتمتة والاستدلال، المجلد 2، أوراق كلاسيكية في المنطق الحسابي 1967–1970، سبرنغر فيرلاج، 1983، الصفحات 159–200.

امتدادات المراسلات

الأصل والنطاق والنتائج

تبدأ مراسلة كاري-هوارد من عدة ملاحظات:

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

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

من جهة ثانية، نظرًا لاحتمالية كتابة برامج غير منتهية، يجب تفسير نماذج الحساب كمال تورنغ (مثل اللغات التي تحتوي على العودية) بعناية، حيث يؤدي التطبيق الساذج للمراسلة إلى منطق غير متسق. أفضل طريقة للتعامل مع الحسابات غير المحدودة من وجهة نظر منطقية ما زالت موضوعًا نشطًا للبحث، لكن أحد الأساليب الشائعة يعتمد على استخدام المونادات لفصل الأكواد التي يمكن إثبات إنهائها عن الأكواد التي قد تكون غير منتهية (وهو أسلوب يعمم كذلك على نماذج حسابية أكثر غنى، وهو نفسه مرتبط بالمنطق المودالي من خلال تمديد طبيعي لتماثل كاري-هوارد). أحد الأساليب الأكثر راديكالية، التي يدافع عنها البرمجة الوظيفية الكاملة، هو القضاء على العودية غير المحدودة (والتنازل عن كمال تورنغ، مع الاحتفاظ بالتعقيد الحسابي العالي)، باستخدام المزيد من التحقق التكراري حيثما يكون السلوك غير المنتهي مرغوبًا فيه.

وعلى صعيد آخر، إذا تم التجريد عن الخصائص الخاصة بكل شكل، فإن التعميم التالي يظهر: "البرهان هو برنامج، والصيغة التي يثبتها هي النوع للبرنامج". بشكل غير رسمي، يمكن رؤية هذا على أنه تمثيل ينص على أن نوع الإرجاع لدالة (أي نوع القيم التي ترجعها الدالة) هو مشابه لمبرهنة منطقية، تكون خاضعة لافتراضات تتعلق بأنواع القيم التي تم تمريرها كوسائط إلى الدالة؛ وأن البرنامج الذي يحسب تلك الدالة هو مشابه لبرهان تلك المبرهنة. هذا يضع أساسًا قويًا للبرمجة المنطقية: "البرهانات يمكن تمثيلها كبرامج، وخاصة كعناصر لامدا"، أو "البرهانات التي يمكن تشغيلها".

وفي هذا السياق، في سنة 1958، لاحظ أن نوعًا معينًا من أنظمة البرهان، والذي يُشار إليه بنظام الاستدلال بأسلوب هيلبرت، يتزامن مع جزء من نموذج حوسبة معروف باسم منطق تجميعي.

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

ومن جهة أخرى، في عام 1934، لاحظ هاسكل كاري أن أنواع المجمّعين يمكن أن تُرى كمخطط-مفردات لمنطق الاستدلال التضميني.

وفي السياق ذاته، أنظمة حساب لامدا المطبوع المشتقة من نموذج كاري-هوارد أدت إلى برامج مثل "Rocq"، حيث يمكن تمثيل البرهانات كبرامج والتحقق منها وتشغيلها.

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

ومن ناحية أخرى، في سنة 1969، لاحظ ويليام آلفين هوارد أن نوعًا آخر من أنظمة البرهان، والذي يُشار إليه بالاستدلال الطبيعي، يمكن تفسيره بشكل مباشر في نسخته منطق الاستدلال كنوع مطبوع من نموذج حوسبة يعرف بتكامل لامدا.

مطابقة كاري-هاوارد-لامبك

وفي هذا الصدد، مطابقة لامبك هي مطابقة لنظريات المعادلات، حيث يتم تجريد الديناميكيات الخاصة بالحساب مثل تقليص بيتا وتطبيع المصطلحات، ولا تمثل تعبيرًا عن هوية تركيبية للهياكل كما هو الحال بالنسبة لمطابقات كاري وهاوارد: أي أن هيكل المورفزم المحدد في فئة مغلقة كارتيسيا لا يمكن مقارنته بهيكل دليل الحكم المقابل في منطق هيلبرت أو الاستدلال الطبيعي. مثلًا، من غير الممكن أن نصرح أو نثبت أن المورفزم يُطَبِّع، أو نثبت نظرية من نوع "تشارش-روسر"، أو نتحدث عن فئة مغلقة كارتيسيا "تطبيعًا قويًا". لتوضيح هذا التمييز، يعاد صياغة الهيكل التركيبي الأساسي للفئات المغلقة كارتيسيا أدناه.

الأشياء (المقترحات/الأنواع) تشمل:

من جانب آخر، أظهر جواكيم لامبك في أوائل السبعينات أن أدلة المنطق القيمي الحدسي والمنظمات اللامدية لأنواع اللامدا ذات الأنواع المجمعة في المنطق التجميعي تشترك في نظرية معادلات مشتركة، وهي نظرية الفئات المغلقة الكارتيسية. يتم استخدام تعبير "مطابقة كاري-هاوارد-لامبك" الآن من قبل بعض الأشخاص للإشارة إلى العلاقات بين المنطق الحدسي، حساب اللامدا ذي الأنواع، والفئات المغلقة الكارتيسية. في ظل هذه المطابقة، يمكن تفسير كائنات الفئة المغلقة كارتيسياً على أنها مقترحات (أنواع)، والمورفismes على أنها استدلالات تربط مجموعة من الافتراضات (سياق الأنواع) إلى نتيجة صحيحة (مصطلح مُصنف بشكل صحيح).

التفسيرات الفلسفية

من جانب آخر، . (الإصدار المبكر المعروض في منطق كولوكويوم '88'، بادوفا. الملخص في JSL 55:425، 1990.)

.

وفي هذا السياق، . (الإصدار المبكر المعروض في الندوة الدولية الرابعة عشرة حول فيتجنشتاين (الاحتفال بمرور المئة عام) التي أقيمت في كيرشبرغ/ويشيل، 13–20 أغسطس 1989.)

تفسير بروير-هايتينغ-كولموغوروف

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

تعميمات

كذلك، وبذلك، فإن تناظر كوري–هوارد الذي يفيد بأن الإثباتات هي عناصر في أنواع مأهولة، يتوسع ليشمل مفهوم تحاول الإثباتات (بوصفها مسارات في الفضاء، إذ يتم تفسير نوع الهوية أو نوع المساواة في نظرية الأنواع كمسار).

من جانب آخر، علاوة على ذلك، يمكن إظهار أن هذه الفئات تقابل الحدود الشعاعية، والتي تلعب دورًا محوريًا في نظرية الأوتار.

علاوةً على ذلك، إن التناظرات المذكورة هنا تمتد أعمق وأبعد بكثير. فمثلًا، تُعمِّم الفئات المغلقة التوحيدية الفئات المغلقة ديكارتيًا. وتُعد اللغة الداخلية لهذه الفئات هي نظام الأنواع الخطية (الذي يقابل المنطق الخطي)، والذي يُعمِّم حساب لامبدا محدود الأنواع بوصفه اللغة الداخلية للفئات المغلقة ديكارتيًا.

كذلك، كما تُستكشف مجموعة موسّعة من التكافؤات ضمن تحاول، حيث تُوسّع نظرية النمط عبر مسلمة التوحيد ("التكافؤ يكافئ المساواة")، ما يتيح استخدام نظرية النمط المُمَثلة طوبولوجيًا كأساس شامل للرياضيات كلها (بما في ذلك نظرية المجموعات والمنطق الكلاسيكي، مع تقديم طرق جديدة لمناقشة بديهية الاختيار والكثير من المفاهيم الأخرى).

المراجع

refs

من جهة ثانية، . (الإصدار الكامل من الورقة المعروضة في منطق كولوكويوم '90'، هلسنكي. الملخص في JSL 56(3):1139–1140، 1991.)

علاوةً على ذلك، . (الإصدار الكامل من ورقة قدمت في منطق كولوكويوم '91'، أوبسالا. الملخص في JSL 58(2):753–754، 1993.)

.

.

كذلك، . (الإصدار الكامل من ورقة قدمت في 2nd WoLLIC'95، ريسيفي. الملخص في مجلة مجموعة الاهتمام في المنطق البحت والتطبيقي 4(2):330–332، 1996.)

  • .
  • .
  • .

وعلى صعيد آخر، . (الإصدار الكامل من ورقة قدمت في LSFA 2010، ناتال، البرازيل.)

.

علاوةً على ذلك، , يتعلق بتكييف الإثباتات كبرامج لتوليد البرامج للمشاكل ذات الحبيبات الكبيرة وبرمجة الأمثل المعتمدة على الأوامر، عبر طريقة يسميها المؤلفون بروتوكول كوري-هوارد. يتضمن مناقشة حول تناظر كوري-هوارد من منظور علوم الكمبيوتر.

,

من جهة ثانية، تطبيق قاعدة القياس (Modus Ponens) مرتين للحصول على إثبات لـ:

أولاً، إثبات النظريات المقابلة لأنواع P وQ.

إضافةً إلى ذلك، بما أن P يتم تطبيقه على Q، يجب أن يكون نوع P من الشكل ونوع Q من الشكل لبعض و. وبالتالي، يمكن فصل النتيجة باستخدام قاعدة القياس.

،

وفي هذا السياق، بشكل عام، الإجراء هو أنه كلما احتوى البرنامج على تطبيق من الشكل (P Q), يجب اتباع الخطوات التالية:

و ليكون (لتفادي تعارض المتغيرات):

  • مركّب التركيب باعتباره إثباتًا لـ (β → α) → (γ → β) → γ → α في منطق هيلبرت
  • كمثال أكثر تعقيدًا، دعنا ننظر إلى النظرية التي تقابل الدالة B. نوع B هو:
  • .
  • B تعادل: (S (K S) K). هذا هو مخططنا لإثبات النظرية:
  • .
  • الخطوة الأولى هي بناء (K S). لجعل مقدم بديهية K يبدو كأنه بديهية S، نضبط ليكون

إضافةً إلى ذلك، هذه هي النظرية التي تتوافق مع نوع (K S). الآن نطبق S على هذا التعبير. نأخذ S على النحو التالي:

في هذا الإطار، بما أن المقدم هنا هو فقط S، يمكن فصل النتيجة باستخدام قاعدة القياس:

الإمكانية في منطق موجهات وأنواع الموناد للتأثيرات

من جانب آخر، حساب (حيث يُقتصر التجريد على λx.E حيث x يحتوي على ظهور واحد على الأقل في E) وCLI تتوافق مع المنطق ذي الصلة.

ومن ناحية أخرى، الحقيقة المحلية (∇) في طوبولوجيا غروثنديك أو المعامل المكافئ "المرن" (◯) لـ بينتون، بييرمان، ودي بايفا (1998) تتوافق مع منطق CL الذي يصف "أنواع الحساب".

أمثلة

المركّب الهوية باعتباره إثباتًا لـ α → α في منطق هيلبرت

كذلك، بفضل مطابقة كوري–هوارد، فإن التعبير النمطي الذي يتوافق نوعه مع صيغة منطقية يكون موازياً لإثبات تلك الصيغة. فيما يلي بعض الأمثلة.

وفي هذا الصدد، كمثال، فلننظر إلى إثبات النظرية . في حساب لامدا، هذا هو نوع دالة الهوية ، وفي المنطق التركيبي يتم الحصول على دالة الهوية بتطبيق S = λfgx.fx(gx) مرتين على K = λxy.x. أي أن . كتوصيف للإثبات، فإن هذا يعني أن الخطوات التالية يمكن استخدامها لإثبات :

وفي السياق ذاته، تطبيق المخطط الثاني للبديهية باستخدام الصيغ ، و للحصول على إثبات لـ:

الأنظمة المتوافقة

ومن جهة أخرى، أنظمة الاستدلال على الطراز هيلبرت الحدسية والمنطق التركيبي الموصوف بالأنواع

وعلى صعيد آخر، كان ذلك في البداية ملاحظة بسيطة في كتاب كوري وفيس عام 1958 حول المنطق التركيبي: الأنواع الأبسط للمنظمات الأساسية K و S في المنطق التركيبي كانت تطابق بشكل مفاجئ مخططات المسلمة α → (β → α) و (α → (β → γ)) → ((α → β) → (α → γ)) المستعملة في أنظمة الاستدلال على الطراز هيلبرت. لهذا السبب، تُسمى هذه المخططات الآن غالباً بالمسلمات K و S. يتم إعطاء أمثلة على البرامج التي يُنظر إليها كدلائل في منطق على طراز هيلبرت أدناه.

ومن ناحية أخرى، يمكن كذلك نقل النتائج المتعلقة بكمال بعض مجموعات المنظمات أو المسلمات. مثلًا، حقيقة أن المنظم X يشكل للمنطق التركيبي (الامتدادي) تعني أن مخطط المسلمة الوحيد

وفي السياق ذاته، بالمقابل، فإن عدم القابلية للإثبات في المنطق الحدسي لـ قانون بيرس يمكن نقله مرة أخرى إلى المنطق التركيبي: لا يوجد مصطلح مبرمج في المنطق التركيبي يمكن أن يُخصص له النوع

  • T هو منظم أساسي؛ أي، ضمن أساس المنظمات الشائع:
  • T هو K:α → (β → α) [حيث α و β يرمزان إلى أنواع وسائطه]، أو
  • T هو S:(α → (β → γ)) → ((α → β) → (α → γ)),
  • T هو تركيب لمصطلحين فرعيين يعتمدان على المتغيرات في Γ.

ومن جهة أخرى، يمكن تمثيل ذلك باستخدام قاعدة الاستدلال، كما في العمود الأيسر في الجدول التالي.

وفي هذا الصدد، إذا تم التقيد بالجزء الحدسي المتعلق بالاستدلالات، فإن الطريقة البسيطة لتشكيل المنطق على طراز هيلبرت هي كما يلي. لنفترض أن Γ هي مجموعة من الصيغ المحدودة، ويُنظر إليها على أنها فرضيات. عندها δ تعتبر "مستنتجة" من Γ، ويرمز لها بـ Γ ⊢ δ في الحالات التالية:

((α → β) → α) → α.

من جهة ثانية، الذي هو النوع الرئيسي لـ X, هو استبدال مناسب للمزيج من مخططات المسلمات

T هو أحد المتغيرات في Γ،

ومن جهة أخرى، يتم إعطاء قواعد التوليد هنا في العمود الأيمن أدناه. ملاحظة كوري ببساطة تفيد أن كلا العمودين يتطابقان بشكل واحد إلى واحد. يقتصر تطابق المنطق الحدسي على المنطق الحدسي مما يعني أن بعض النتائج المبدئية، مثل قانون بيرس ((α → β) → α) → α، مستبعدة من التطابق.

إضافةً إلى ذلك، رؤية ذلك على مستوى أكثر تجريدًا، يمكن إعادة صياغة المطابقة كما هو موضح في الجدول التالي. خاصة، فإن نظرية الاستدلال الخاصة بالمنطق على طراز هيلبرت تطابق عملية إزالة التجريد في المنطق التركيبي.

  • δ هي حالة من مخطط المسلمة؛ أي، ضمن أكثر أنظمة المسلمات شيوعاً:
  • δ تأخذ الشكل α → (β → α)، أو
  • δ تأخذ الشكل (α → (β → γ)) → ((α → β) → (α → γ)),

ومن جهة أخرى، δ تتبع بالاستدلال، أي، لوجود α، كل من α → δ و α مستنتجان بالفعل من Γ (هذه هي قاعدة قياس استثنائي)

من جانب آخر، (((α → (β → γ)) → ((α → β) → (α → γ))) → ((δ → (ε → δ)) → ζ)) → ζ,

ومن جهة أخرى، بفضل هذه المطابقة، يمكن نقل النتائج من المنطق التركيبي إلى منطق الطراز هيلبرت والعكس صحيح. مثلًا، يمكن نقل مفهوم تقليص المصطلحات في المنطق التركيبي إلى منطق الطراز هيلبرت، ويتيح ذلك طريقة لتحويل الأدلة بشكل رسمي إلى أدلة أخرى لنفس العبارة. يمكن كذلك نقل مفهوم المصطلحات العادية إلى مفهوم الأدلة العادية، مما يعبر عن أن فرضيات المسلمات لا تحتاج أبداً إلى أن تكون مفصولة بالكامل (لأنه في حالة أخرى يمكن أن يحدث تبسيط).

كذلك، يمكن صياغة المنطق التركيبي الموصوف بالأنواع باستخدام بنية مشابهة: لنفترض أن Γ هي مجموعة من المتغيرات المحدودة، مع توضيح أنواعها. سيكون للعبارة T (كذلك مع توضيح نوعها) اعتماد على هذه المتغيرات [Γ ⊢ T:δ] عندما:

δ هي فرضية، أي هي صيغة من Γ،

————————————————————————————————————

a:β → α, b:γ → β ⊢ λ g. a (b g) : γ → α

المنطق الكلاسيكي وموصلات التحكم

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

ومن ناحية أخرى، في زمن كاري، وأيضًا في زمن هوارد، كانت مطابقة الأدلة-البرامج تتعلق فقط بـ المنطق الحدسي، أي منطق لا يمكن فيه استنتاج قانون بيرس. أصبح من الواضح أن امتداد المطابقة ليشمل قانون بيرس وبالتالي المنطق الكلاسيكي كان من خلال أعمال جريفين حول تخصيص المشغلين الذين يلتقطون سياق التقييم لتنفيذ البرنامج بحيث يمكن إعادة تثبيت هذا السياق لاحقًا. المطابقة الأساسية على طراز كاري–هوارد للمنطق الكلاسيكي موضحة أدناه. لاحظ المطابقة بين ترجمة النفي المزدوج المستعملة لتحويل الأدلة الكلاسيكية إلى المنطق الحدسي والاستمرارية المستعملة لتحويل مصطلحات لامدا التي تشمل التحكم إلى مصطلحات لامدا نقية. بشكل أكثر تحديدًا، فإن ترجمات نمط تمرير الاستمرار عند الاستدعاء حسب الاسم تتعلق بـ أندريه كولموغوروف ترجمة النفي المزدوج وترجمات نمط تمرير الاستمرار عند الاستدعاء حسب القيمة تتعلق بنوع من الترجمة المزدوجة للنفي التي وضعها كورودا.

الأوراق الاصطناعية

  • , مساهمة دي بروين بنفسه.
  • , يحتوي على مقدمة تركيبية إلى تناظر كوري–هوارد.
  • , يحتوي على مقدمة تركيبية إلى تناظر كوري–هوارد.

كتب

وفي هذا الصدد، , يتناول تكييف برنامج توليد البرامج من الإثباتات لحل مشكلات تطوير البرامج التقريرية والبرمجة الموجّهة بالأوامر، عبر طريقة يسميها المؤلفون "بروتوكول كوري–هوارد". يتضمن مناقشة لتناظر كوري–هوارد من منظور علوم الحاسوب.

.

.

علاوةً على ذلك، , يُعيد نشر الأوراق الرائدة لكوري-فايس وهوارد، وورقة لـ دي بروين وعدد قليل من الأوراق الأخرى.

وفي هذا الصدد، , ملاحظات في نظرية الإثبات ونظرية الأنواع، تتضمن عرضًا لتناظر كوري–هوارد، مع تركيز على تناظر الصيغ-كأنواع.

, ملاحظات في نظرية الإثبات مع عرض لتناظر كوري–هوارد.

دور دي بروين

في هذا الإطار، استعمل نيكولاس غوفيرت دي بروين تدوين اللامدا لتمثيل أدلة نظام التحقق من النظريات أوتومات، ويمثل المقترحات كـ "فئات" من أدلتها. في أواخر الستينات، في نفس الفترة التي كتب فيها هاوارد مخطوطته؛ كان دي بروين على الأرجح غير مدرك لأعمال هاوارد، وذكر المطابقة بشكل مستقل (سورنسن وأورزيشين [1998] 2006، الصفحات 98–99). يميل بعض الباحثين إلى استخدام مصطلح "مطابقة كاري-هاوارد-دي بروين" بدلاً من "مطابقة كاري-هاوارد".

قراءة إضافية

هوارد عن كوري-هوارد

وصلات خارجية

من جهة ثانية، — gives a categorical view of "what happens" in the Curry–Howard correspondence.

التحقيق القابل للتنفيذ

ومن جهة أخرى، قائمة ستيفن كول كلين لفكرة التحقيق القابل للتنفيذ تقسم الأدلة في الحساب الحدسي إلى زوج من دالة تكرارية ودليل على صيغة تعبر عن أن الدالة التكرارية "تحقق" أي أنها تقوم بتجسيد التمويهات والمحددات الوجودية للصيغة الأصلية بحيث تصبح الصيغة صحيحة.

ومن جهة أخرى، جورج كرايسل يعدل التحقيق القابل للتنفيذ ليتناسب مع المنطق الحدسي من الرتبة الأعلى ويظهر أن مصطلح اللامدا ذو الأنواع البسيطة المستخرج بشكل تكراري من الدليل يحقق الصيغة الأصلية. في حالة المنطق القيمي، يتزامن هذا مع بيان هاوارد: المصطلح المستخرج من اللامدا هو الدليل نفسه (مُعتبرًا كمصطلح لامدا غير مُصنف) وبيان التحقيق هو إعادة صياغة لحقيقة أن المصطلح المستخرج من اللامدا يحتوي على النوع الذي تمثل الصيغة (مُعتبرًا كنوع).

وفي هذا السياق، تفسير كورت غودل تفسير ديالكتيكا يحقق (تمديدًا) الحساب الحدسي باستخدام الدوال القابلة للحساب. العلاقة مع حساب اللامدا غير واضحة، حتى في حالة الاستدلال الطبيعي.

,

كذلك، تطبيق المخطط الأول للبديهية مرة ثانية باستخدام و للحصول على إثبات لـ:

————————————————————————————————————————

a:β → α ⊢ λ b. λ g. a (b g) : (γ → β) → γ → α

تطابق كوري-هوارد في هاسكل

ومن ناحية أخرى، ذا مونايد ريدر 6: مغامرات في أرض الكلاسيك: كوري-هوارد في هاسكل، قانون بيرس

,

من جهة ثانية، تطبيق المخطط الأول للبديهية مرة واحدة باستخدام و للحصول على إثبات لـ:

حساب المتتاليات

المطابقات المتعلقة بالأدلة-البرامج

وفي هذا السياق، يمكن تحديد مطابقة الأدلة-البرامج للصيغة المعروفة بـ حساب المتتاليات لـ غيرهارت غنتزن، لكن لا يوجد تطابق مع نموذج معين مسبقًا للحساب كما كان الحال في استدلالات هيلبرت ونظام الاستدلال الطبيعي.

وعلى صعيد آخر، يتميز حساب المتتاليات بوجود قواعد إدخال لليسار، وقاعدة إدخال لليمين، وقاعدة القطع التي يمكن إلغاؤها. هيكل حساب المتتاليات يتعلق بحساب يكون هيكله قريبًا من هيكل بعض الآلات المجردة. المطابقة غير الرسمية هي كما يلي:

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.