المشاكل غير القابلة للحسم
| English | العربية |
|---|---|
| cannot/ˈkænɒt/ | لا يمكن |
| decidable/dɪˈsaɪdəbl/ | قابل للقرارة |
| undecidable/ˌʌndɪˈsaɪdəbl/ | غير قابل للحسم |
| limit/ˈlɪmɪt/ | حد |
| inefficient/ɪnɪˈfɪʃənt/ | غير فعالة |
ليس كل مشكلة قابلة للحل
- ليست كل مشكلة يمكن حلها بواسطة الحاسوب، حتى من حيث المبدأ.
- لمعرفة السبب، نصنف المشاكل إلى نوعين.
- نوع واحد يمكن للحاسوب دائماً الإجابة عليه؛ والنوع الآخر لا يستطيع ذلك.
- هذا حقيقة مثبتة في علوم الحاسوب، وليس فجوة قد نمولها يوماً ما.
المشكلة القابلة للحسم هي تلك التي:
"هل n زوجي؟" مشكلة قابلة للحسم — يمكن إجابتها دائمًا.
المسائل القابلة للقرر
- المسألة القابلة للقرر هي تلك التي تمتلك خوارزمية تعطي إجابة صحيحة بنعم أو لا لكل حالة على حدة.
- "هل هذا العدد زوجي؟" مسألة قابلة للقرر — فاختبار بسيط يعطي إجابة صحيحة دائماً.
- "هل هذا العدد أولي؟" مسألة قابلة للقرر أيضاً، حتى لو كانت بطيئة للأعداد الضخمة.
- إذا وُجدت خوارزمية صحيحة لـكل حالة، فإن المسألة تُعدّ قابلة للقرر.
قابلة للحسم أم غير قابلة للحسم؟
المشكلة القابلة للحسم لها خوارزمية تجيب بشكل صحيح دائماً لكل حالة؛ أما غير القابلة للحسم فلا توجد مثل هذه الخوارزمية — فهي مستحيلة وليست مجرد بطيئة.
المشكلة غير القابلة للحسم:
بعض الحالات تقهر كل برنامج محتمل.
الحكم فيما إذا كان أي برنامج معطى سيتوقف عن التشغيل نهائياً هو:
لا توجد خوارزمية واحدة تجيب بشكل صحيح لكل برنامج.
عدم قابلية الحسم تحدد حداً صعباً ______ لما يمكن للحوسبة تحقيقه.
بعض الأسئلة ليس لها خوارزمية عامة.
المسائل غير القابلة للقرر
- المسألة غير القابلة للقرر هي التي لا توجد خوارزمية تحل جميع حالاتها بشكل صحيح.
- بغض النظر عن مدى ذكاء البرنامج، ستظل هناك بعض الحالات تتغلب عليه.
- المثال الكلاسيكي: تحديد ما إذا كان أي برنامج مُعطى سيتوقف عن التشغيل أبداً.
- عدم القابلية للقرر هو حد لما يمكن للحوسبة تحقيقه — فبعض الأسئلة ليس لها خوارزمية عامة.
غير قابل للحسم وبطيء فقط يعنيان نفس الشيء.
البطء يمكن حله ببطء؛ عدم قابلية الحسم لا يمكن حلها لكل الحالات على الإطلاق.
اختبار ما إذا كان العدد أولياً هو مشكلة قابلة للحسم، حتى لو كانت بطيئة للأعداد الهائلة.
الخوارزمية تجيب دائمًا؛ البطء ليس نفسه استحالة.
عدم القابلية للقرر ليست مجرد بطء
- لا تخلط بين المسألة غير القابلة للقرر وبين المسألة غير الفعالة فقط.
- المسألة غير الفعالة يمكن حلها، ولكن ببطء. أما المسألة غير القابلة للقرر فلا يمكن حلها لجميع الحالات على الإطلاق.
الأولية مقابل التوقف. اختبار ما إذا كان العدد أولياً هو مسألة قابلة للقرر — فالخوارزمية تعطي إجابة دائماً، حتى لو كانت بطيئة للأعداد الضخمة. لكن تحديد ما إذا كان أي برنامج سيتوقف هو مسألة غير قابلة للقرر: فلا توجد خوارزمية واحدة تجيب بشكل صحيح لجميع البرامج. البطء ليس كونه مستحيلاً.
المسألة القابلة للقرر تمتلك خوارزمية تجيب دائماً بشكل صحيح ("هل n زوجي؟"، "هل n أولي؟"). أما المسألة غير القابلة للقرر فلها لا خوارزمية من هذا النوع لجميع الحالات (هل سيتوقف البرنامج؟) — وهو حد حقيقي للحوسبة. عدم القابلية للقرر يعني أنه لا يمكن حلها على الإطلاق، وليس مجرد عدم فعالية (بطء).