ما هي أوجه القصور في إجراءات قرار روبنسون؟

Question

paulson et alii. من LCF إلى ISABELLE / HOL قل:

دقة منطق الدرجة الأولى، كاملة من حيث المبدأ ولكن بشكل متكرر مخيب للآمال في الممارسة.

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

القرار هو طريقة إثبات إكمال إكمال Refutationaly: يمكن استنتاج التناقض (I.E.، البند الفارغ) من أي مجموعة غير مرضية من البنود.

من ويكيبيديا:

حاول إثبات صيغة الطلب الأول الراضية لأنها غير مرضية قد تؤدي إلى حساب غير قابل للتطبيق

لماذا هذا مخيب للآمال؟

Answer 1

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

مثال مشهور هو ترميز من Pigeon Hole Presortle ل $ N $ الثقوب في منطق الاقتراح (وهو البيان "؛ $ n + 1 $ لا يمكن أن يصلح الحمام في $ n $ holes دون التكرارات). لا يوجد دليل على هذا البيان باستخدام الدقة فقط في الوقت المناسب في الوقت الأسي في $ n $ .

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

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