Undecidable Problems
مُقدَّم| English | المعنى |
|---|---|
| cannot/ˈkænɒt/ | لا يمكن |
| decidable/dɪˈsaɪdəbl/ | قابلة للتحديد |
| undecidable/ˌʌndɪˈsaɪdəbl/ | غير قابلة للتحديد |
| limit/ˈlɪmɪt/ | الحد |
| inefficient/ɪnɪˈfɪʃənt/ | غير فعال |
ليس كل مشكلة قابلة للحل
- ليست كل مشكلة يمكن حلها بواسطة الحاسوب، حتى من حيث المبدأ.
- لمعرفة السبب، نصنف المشاكل إلى نوعين.
- نوع واحد يمكن للحاسوب دائماً الإجابة عليه؛ والنوع الآخر لا يستطيع ذلك.
- هذا حقيقة مثبتة في علوم الحاسوب، وليس فجوة قد نمولها يوماً ما.
A decidable problem is one where:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
"Is n even?" is decidable — always answerable.
المسائل القابلة للقرر
- المسألة القابلة للقرر هي تلك التي تمتلك خوارزمية تعطي إجابة صحيحة بنعم أو لا لكل حالة على حدة.
- "هل هذا العدد زوجي؟" مسألة قابلة للقرر — فاختبار بسيط يعطي إجابة صحيحة دائماً.
- "هل هذا العدد أولي؟" مسألة قابلة للقرر أيضاً، حتى لو كانت بطيئة للأعداد الضخمة.
- إذا وُجدت خوارزمية صحيحة لـكل حالة، فإن المسألة تُعدّ قابلة للقرر.

المسائل القابلة للحسم وغير القابلة للحسم
Decidable or undecidable?
A decidable problem has an algorithm that always answers correctly for every case; an undecidable one has no such algorithm — being impossible, not merely slow.
An undecidable problem:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Some questions simply have no general algorithm.
المسائل غير القابلة للقرر
- المسألة غير القابلة للقرر هي التي لا توجد خوارزمية تحل جميع حالاتها بشكل صحيح.
- بغض النظر عن مدى ذكاء البرنامج، ستظل هناك بعض الحالات تتغلب عليه.
- المثال الكلاسيكي: تحديد ما إذا كان أي برنامج مُعطى سيتوقف عن التشغيل أبداً.
- عدم القابلية للقرر هو حد لما يمكن للحوسبة تحقيقه — فبعض الأسئلة ليس لها خوارزمية عامة.
Undecidable and merely inefficient (slow) mean the same thing.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Inefficient can be solved slowly; undecidable cannot be solved for every case at all.
Testing whether a number is prime is undecidable because it can be slow for huge numbers.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
عدم القابلية للقرر ليست مجرد بطء
- لا تخلط بين المسألة غير القابلة للقرر وبين المسألة غير الفعالة فقط.
- المسألة غير الفعالة يمكن حلها، ولكن ببطء. أما المسألة غير القابلة للقرر فلا يمكن حلها لجميع الحالات على الإطلاق.
الأولية مقابل التوقف. اختبار ما إذا كان العدد أولياً هو مسألة قابلة للقرر — فالخوارزمية تعطي إجابة دائماً، حتى لو كانت بطيئة للأعداد الضخمة. لكن تحديد ما إذا كان أي برنامج سيتوقف هو مسألة غير قابلة للقرر: فلا توجد خوارزمية واحدة تجيب بشكل صحيح لجميع البرامج. البطء ليس كونه مستحيلاً.
المسألة القابلة للقرر تمتلك خوارزمية تجيب دائماً بشكل صحيح ("هل n زوجي؟"، "هل n أولي؟"). أما المسألة غير القابلة للقرر فلها لا خوارزمية من هذا النوع لجميع الحالات (هل سيتوقف البرنامج؟) — وهو حد حقيقي للحوسبة. عدم القابلية للقرر يعني أنه لا يمكن حلها على الإطلاق، وليس مجرد عدم فعالية (بطء).