مشكلة غير قابلة للحل

في نظرية الحوسبة ونظرية التعقيد الحسابي ، تُعرَّف المسألة غير القابلة للحسم بأنها مسألة قرار ثبت استحالة بناء خوارزمية لها تؤدي دائمًا إلى إجابة صحيحة بنعم أو لا. تُعد مسألة التوقف مثالًا على ذلك: إذ يمكن إثبات عدم وجود خوارزمية تحدد بشكل صحيح ما إذا كان برنامج ما سيتوقف في نهاية المطاف عند تشغيله. ^{[ 1 ]}

مشكلة القرار هي سؤال يتطلب، لكل مدخل في مجموعة غير منتهية من المدخلات، إجابة "نعم" أو "لا". ^{[ 2 ]} يمكن أن تكون هذه المدخلات أرقامًا (على سبيل المثال، مشكلة القرار "هل المدخل عدد أولي ؟") أو قيمًا من نوع آخر، مثل سلاسل لغة رسمية .

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

تُسمى مسألة القرار A قابلة للتقرير أو قابلة للحل فعليًا إذا كانت المجموعة المُصاغة لـ A مجموعةً تكرارية . وإلا، تُسمى A غير قابلة للتقرير. تُسمى المسألة قابلة للتقرير جزئيًا، أو شبه قابلة للتقرير، أو قابلة للحل، أو قابلة للإثبات إذا كانت A مجموعةً قابلة للتعداد التكراري . ^{[ ملاحظة 1 ]}

في نظرية الحوسبة ، تُعتبر مشكلة التوقف مشكلة قرار يمكن صياغتها على النحو التالي:

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

أثبت آلان تورينج في عام 1936 أنه من المستحيل بالضرورة وجود خوارزمية عامة تعمل على آلة تورينج تحل مشكلة التوقف لجميع أزواج البرنامج والمدخلات الممكنة. وبالتالي، فإن مشكلة التوقف غير قابلة للحل بالنسبة لآلات تورينج.

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

يمكن إثبات الصيغة الأضعف للنظرية من عدم قابلية حسم مسألة التوقف كما يلي. ^{[ 3 ]} لنفترض أن لدينا مجموعة بديهيات فعالة سليمة (وبالتالي متسقة) وكاملة لجميع عبارات منطق الرتبة الأولى الصحيحة حول الأعداد الطبيعية . عندئذٍ، يمكننا بناء خوارزمية تُحصي جميع هذه العبارات. هذا يعني وجود خوارزمية N ( n ) التي، عند إعطائها عددًا طبيعيًا n ، تحسب عبارة منطقية صحيحة من الرتبة الأولى حول الأعداد الطبيعية، وأنه لكل عبارة صحيحة، يوجد على الأقل عدد طبيعي واحد n بحيث تُنتج N ( n ) تلك العبارة. الآن، لنفترض أننا نريد تحديد ما إذا كانت الخوارزمية ذات التمثيل a تتوقف عند المدخل i . نعلم أنه يمكن التعبير عن هذه العبارة بعبارة منطقية من الرتبة الأولى، ولتكن H ( a , i ). بما أن مجموعة البديهيات كاملة، فإنه يترتب على ذلك إما وجود عدد طبيعي n بحيث N ( n ) = H ( a , i ) أو وجود عدد طبيعي n ′ بحيث N ( n ′ ) = ¬H ( a , i ). لذا، إذا كررنا العملية على جميع قيم n حتى نجد إما H ( a , i ) أو نفيها، فسنتوقف دائمًا، وعلاوة على ذلك، ستكون الإجابة التي نحصل عليها صحيحة (بحكم سلامة المنطق). هذا يعني أن لدينا خوارزمية لحل مشكلة التوقف. وبما أننا نعلم أنه لا يمكن وجود مثل هذه الخوارزمية، فإن افتراض وجود بديهية سليمة وكاملة وفعالة لجميع عبارات منطق الرتبة الأولى الصحيحة حول الأعداد الطبيعية هو افتراض خاطئ.

يمكن ربط المسائل غير القابلة للحسم بمواضيع مختلفة، مثل المنطق ، والآلات المجردة ، والطوبولوجيا . ونظرًا لوجود عدد لا يُحصى من المسائل غير القابلة للحسم، ^{[ ملاحظة 2 ]} فإن أي قائمة، حتى لو كانت ذات طول لانهائي ، تكون بالضرورة غير مكتملة.

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

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

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

كانت إحدى أولى المشكلات التي يُشتبه في أنها غير قابلة للحل، بالمعنى الثاني للكلمة، هي مسألة الكلمات الخاصة بالمجموعات ، والتي طرحها ماكس دين لأول مرة عام 1911، والتي تسأل عما إذا كانت هناك مجموعة معروضة بشكل محدود لا توجد لها خوارزمية لتحديد ما إذا كانت كلمتان متكافئتين. وقد أثبت سيرجي نوفيكوف صحة ذلك عام 1955. ^{[ 4 ]}

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

تم إثبات عدم قابلية حل مسألة هيلبرت العاشرة ، التي طُرحت عام 1900 كتحدٍّ لعلماء الرياضيات في القرن التالي، على يد يوري ماتياسيفيتش عام 1970. سعى تحدي هيلبرت إلى إيجاد خوارزمية تُحدد جميع حلول معادلة ديوفانتية . تُعدّ المعادلة الديوفانتية حالةً أعمّ من نظرية فيرما الأخيرة ؛ حيث نسعى لإيجاد الجذور الصحيحة لكثير الحدود في أي عدد من المتغيرات ذات المعاملات الصحيحة. بما أن لدينا معادلة واحدة فقط ولكن n من المتغيرات، فإن عددًا لا نهائيًا من الحلول موجود (ويسهل إيجاده) في المستوى المركب ؛ ومع ذلك، تصبح المسألة مستحيلة إذا اقتصرت الحلول على القيم الصحيحة للمتغيرات. بيّن ماتياسيفيتش عدم قابلية حل هذه المسألة عن طريق تحويل المعادلة الديوفانتية إلى مجموعة قابلة للتعداد بشكل متكرر، واستنادًا إلى نظرية عدم الاكتمال لغودل. ^{[ 5 ]}

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

في عام 1973، أظهر ساهارون شيلاه أن مشكلة وايتهيد في نظرية الزمر غير قابلة للتقرير، بالمعنى الأول للكلمة، في نظرية المجموعات القياسية. ^{[ 6 ]}

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

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

إن نظرية جودستين هي بيان حول نظرية رامزي للأعداد الطبيعية التي أظهر كيربي وباريس أنها غير قابلة للتقرير في حساب بيانو.

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

في عام 2007، أثبت الباحثان كورتز وسيمون، بالاستناد إلى عمل سابق قام به جيه إتش كونواي في السبعينيات، أن التعميم الطبيعي لمسألة كولاتز غير قابل للتقرير. ^{[ 7 ]}

في عام 2019، قام بن ديفيد وزملاؤه بإنشاء مثال لنموذج تعلم (يُسمى EMX)، وأظهروا مجموعة من الدوال التي لا يمكن تحديد قابليتها للتعلم في EMX في نظرية المجموعات القياسية. ^{[ 8 ] [ 9 ]}

• قابلية الحسم (المنطق)
• مشكلة اتخاذ القرار
• إثبات الاستحالة
• عدم المعرفة
• مشكلة معقدة