💻 computer science

A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem

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

المؤلفون الأصليون: Jonathan Brossard

نُشر 2026-04-21

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Jonathan Brossard

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

الصورة الكبيرة: عن ماذا تتحدث هذه الورقة؟

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

نظرية رايس (Rice's Theorem) تقول: لا توجد مثل هذه الآلة السحرية. إذا كانت السمة تتعلق بما يفعله البرنامج (سلوكه) وليست سمة تافهة (مثل "هل يعمل على جهاز كمبيوتر؟")، فلا يمكنك أبدًا بناء كاشف مثالي لها.

مشكلة التوقف (The Halting Problem) هي النسخة الأكثر شهرة من هذه النظرية: لا يمكنك أبدًا بناء برنامج يتنبأ بدقة ما إذا كان برنامج آخر سيتوقف عن العمل أم سيظل عالقًا في حلقة مفرغة (Infinite Loop).

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

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

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

الفكرة الجوهرية: بناء "الشاهد المزدوج" (The Two-Witness Construction)

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

1. الإعداد: لغز ديوفانتين (The Diophantine Puzzle)

أولاً، تخيل لغزًا رياضيًا صعبًا للغاية يسمى معادلة ديوفانتين. إنها معادلة حيث يتعين عليك إيجاد حلول للأعداد الصحيحة (مثل $x^2 + y^2 = z^2$ ).

القاعدة: نحن نعلم من نظرية شهيرة (MRDP) أنه لا توجد خوارزمية عامة لتحديد ما إذا كانت هذه الألغاز لها حل أم لا. من المستحيل حلها جميعًا.

2. الفخ: التوأمان ( $S_0$ و $S_1$ )

يصنع بروسارد مصنعًا خاصًا. لأي لغز رياضي تعطيه له، يقوم المصنع ببناء برنامجين كمبيوتريين (لنسمهما التوأم أ والتوأم ب).

السيناريو 1: اللغز له حل.
- التوأم أ مبرمج ليتصرف مثل برنامج "سيء" (واحد يفشل في اختبارك).
- التوأم ب مبرمج ليتصرف مثل برنامج "جيد" (واحد يجتاز اختبارك).
- النتيجة: إذا سألت الكاشف، "هل التوأم أ جيد؟" سيقول لا. "هل التوأم ب جيد؟" سيقول نعم. الكاشف يرى فرقًا!
السيناريو 2: اللغز ليس له حل.
- كل من التوأم أ والتوأم ب يعلقان في حلقة مفرغة. كلاهما يتصرفان بشكل متطابق تمامًا: لا يتوقفان أبدًا.
- النتيجة: إذا سألت الكاشف، "هل التوأم أ جيد؟" و"هل التوأم ب جيد؟"، يجب أن يعطي نفس الإجابة لكليهما. لماذا؟ لأنهما يتصرفان بشكل متطابق. لا يهم إذا كان الكاشف يعتقد أن "الحلقات المفرغة جيدة" أو "الحلقات المفرغة سيئة"؛ يجب أن يكون متسقًا.

3. الخدعة السحرية: الفرق

الآن، تخيل وجود "كاشف سحري" يدعي أنه يستطيع تحديد ما إذا كان أي برنامج يمتلك سمة معينة.

يقول بروسارد: "دعونا نغذي التوأم أ والتوأم ب لهذا الكاشف وننظر إلى الفرق في إجاباتهما".

إذا كان اللغز الرياضي له حل، فإن الكاشف يعطي إجابات مختلفة (1 و 0). الفرق هو 1.
إذا كان اللغز الرياضي ليس له حل، فإن التوأم أ والتوأم ب يعطيان نفس الإجابة (0 و 0، أو 1 و 1). الفرق هو 0.

الاستنتاج:
إذا كان "الكاشف السحري" موجودًا بالفعل، فيمكنك استخدامه لحل اللغز الرياضي! ستقوم فقط بفحص الفرق بين التوأمين.

الفرق = 1 $\leftarrow$ اللغز له حل.
الفرق = 0 $\leftarrow$ اللغز ليس له حل.

ولكننا نعلم بالفعل (من نظرية MRDP) أن لا أحد يمكنه حل كل هذه الألغاز الرياضية. لذلك، فإن "الكاشف السحري" لا يمكن أن يوجد.

لماذا هذا البرهان "إنشائي"؟

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

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

تشبيه "الوقود" (تفصيل تقني مبسط)

تستخدم الورقة مفهوم "النماذج ذات المؤشر بالخطوات" أو "الوقود".

تخيل أن كل برنامج يأتي مع خزان من الوقود.
في كل مرة يقوم فيها البرنامج بخطوة، فإنه يحرق وحدة واحدة من الوقود.
إذا نفد الوقود ولم ينتهِ، فإنه يتوقف (يتباعد/diverges).
إذا انتهى قبل نفاد الوقود، فإنه ينجح.

الحيلة الذكية للمؤلف هي أن "التوائم" لا تعمل للأبد فحسب؛ بل تنتظر لترى ما إذا كان اللغز الرياضي قد حُلَّ أم لا.

إذا حُلَّ اللغز في الخطوة 100، فإن التوائم تغير سلوكها تمامًا عند الخطوة 100.
إذا لم يُحل اللغز أبدًا، فلن يغير التوائم سلوكهما؛ سيستمران في حرق الوقود للأبد.

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

التأثير في العالم الحقيقي

لماذا يهم هذا؟

التحقق من البرمجيات (Software Verification): الأدوات الحديثة (مثل تلك المستخدمة للتحقق من السيارات ذاتية القيادة أو برمجيات البنوك) تستخدم "المنطق الإنشائي". لا يمكنها الوثوق في البراهن التي تعتمد على "ربما يكون صحيحًا، وربما يكون خاطئًا". تقدم هذه الورقة برهانًا يمكن لهذه الأدوات استخدامه والوثوق به فعليًا.
لا حاجة لـ "السحر": تُظهر الورقة أن استحالة التنبؤ بسلوك البرنامج ليست مجرد خدعة منطقية غريبة؛ بل هي مرتبطة بعمق بالصعوبة الجوهرية لحل ألغاز الأعداد.
مشكلة التوقف (The Halting Problem): بمجرد إثبات نظرية رايس بهذه الطريقة، تصبح مشكلة التوقف (هل يمكننا معرفة ما إذا كان البرنامج سيتوقف؟) نتيجة تلقائية بسيطة. لست بحاجة إلى برهان منفصل ومعقد لها.

ملخص التشبيه

تخيل أنك تحاول إثبات أنه لا يمكن لأحد التنبؤ بالطقس بدقة.

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

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

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

1. بيان المشكلة

تتناول الورقة التحدي التأسيسي المتمثل في إثبات مبرهنة رايس (Rice's Theorem) ومشكلة التوقف (Halting Problem) ضمن المنطق الحدسي (البنائي).

مبرهنة رايس: تنص على أنه لا يمكن تقرير أي خاصية دلالية (semantic property) غير بديهية للبرامج.
مشكلة التوقف: هي حالة خاصة من مبرهنة رايس تتعلق بما إذا كان البرنامج ينتهي أم لا.
العقبة: تعتمد البراهين الكلاسيكية لهذه المبرهنات بشكل كبير على قانون الوسط المستبعد (LEM) والتشخيص (diagonalization) (المرجعية الذاتية). وتتطلب تحديداً:
1. التأكيد على أن برنامجاً معيناً إما يتوقف أو يستمر في العمل للأبد (LEM).
2. إجراء تقسيم للحالات (case split) حول ما إذا كان البرنامج الذي "يستمر دائماً في العمل" ( $\bot$ ) يحقق الخاصية $P$ (تقسيم $P(\bot)$ ).
3. استخدام مبرهنات النقطة الثابتة (مبرهنة التكرار) لبناء برامج ذات مرجعية ذاتية.

هذه الخطوات الكلاسيكية تمنع البراهين من أن تكون صالحة في المنطق الحدسي، وهو أمر ضروري لأنظمة التحقق الرسمي مثل Coq/Rocq حيث يجب أن تحمل البراهين محتوى حوسبي (على سبيل المثال، لاستخراج البرامج).

2. المنهجية

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

المكونات التقنية الرئيسية:

بناء الشاهد المزدوج (Two-Witness Construction): بدلاً من بناء برنامج واحد يسلك سلوكاً مختلفاً بناءً على مقرر (decider) افتراضي، يقوم المؤلف ببناء زوج من البرامج ( $S^0_D, S^1_D$ $S_{D}^{0}, S_{D}^{1}$ ) لكل متعدد حدود ديوفانتي (Diophantine polynomial) $D$ $D$ .
- المدخلات: متعدد حدود ديوفانتي $D$ وشاهدان للبرامج $e_0$ (لا يحقق الخاصية $P$ ) و $e_1$ (يحقق الخاصية $P$ ).
- السلوك:
  - إذا كان لـ $D$ حل: يتصرف $S^0_D$ مثل $e_0$ ويتصرف $S^1_D$ مثل $e_1$ .
  - إذا لم يكن لـ $D$ حل: كلاهما $S^0_D$ و $S^1_D$ يستمران في العمل بشكل متطابق (يتصرفان مثل $\bot$ ).
دالة الفرق ( $\delta_D$ ): المقرر الافتراضي $Decide_P$ $D ec i d e_{P}$ سيعيد قيمتين مختلفتين لـ $S^1_D$ $S_{D}^{1}$ و $S^0_D$ $S_{D}^{0}$ إذا كان $D$ $D$ قابلاً للحل، وقيمتين متماثلتين إذا كان $D$ $D$ غير قابل للحل.
- نُعرف $\delta_D = Decide_P(S^1_D) - Decide_P(S^0_D)$ .
- إذا كان $D$ قابلاً للحل، فإن $\delta_D = 1$ .
- إذا كان $D$ غير قابل للحل، فإن $\delta_D = 0$ (لأن $S^0_D \equiv S^1_D \equiv \bot$ ، وبالتالي $P(S^0_D) \iff P(S^1_D)$ بموجب التكافؤ الامتدادي، بغض النظر عن القيمة الحقيقية لـ $P(\bot)$ ).
نموذج الفهرسة بالخطوات (Step-Indexed Model): يستخدم الصياغة نموذجاً حوسبياً مفهرساً بالخطوات (البرامج هي دوال $N \to (N \to \text{option } N)$ ). يسمح هذا بتعريف بنائي لـ التكافؤ الملحوظ ( $\phi_e \simeq \phi_f$ ) دون افتراض أن البرنامج يجب أن يتوقف أو يستمر في العمل.
تجنب قانون الوسط المستبعد (LEM):
- لا تقسيم لـ $P(\bot)$ : عندما يكون $D$ غير قابل للحل، تكون البرامج متطابقة ملحوظاً. يعتمد البرهان على التكافؤ الامتدادي ( $P(S^0_D) \iff P(S^1_D)$ ) بدلاً من معرفة القيمة المحددة لـ $P(\bot)$ .
- لا تشخيص: يتم بناء البرامج $S^b_D$ بشكل صريح من $D$ وبت (bit) $b$ . لا تُستخدم مبرهنة النقطة الثابتة أو المرجعية الذاتية.
- بنية الاستلزام: تم هيكلة البرهان كاستلزامين منفصلين:
  1. $D$ قابل للحل $\implies \delta_D = 1$
  2. $D$ غير قابل للحل $\implies \delta_D = 0$
    وهو لا يقرر أبداً التخيير (disjunction) بين " $D$ قابل للحل أو غير قابل للحل".

3. المساهمات الرئيسية

برهان بنائي لمبرهنة رايس: أول برهان لمبرهنة رايس صالح في المنطق الحدسي لا يعتمد على مشكلة التوقف كخطوة وسيطة. إنه يلغي جميع استخدامات LEM والتشخيص.
الاختزال المباشر إلى MRDP: يثبت اختزالاً مباشً من مبرهنة رايس إلى عدم قابلية تقرير المعادلات الديوفانتية (مسألة هيلبرت العاشرة)، مع اعتبار مشكلة التوقف نتيجة مترتبة عليها.
الصياغة في Rocq (Coq): تمت صياغة البرهان بأكمله في مساعد الإثبات Rocq (Coq 8.18+).
- صفر بديهيات كلاسيكية: التطوير يستخدم صفر بديهيات كلاسيكية.
- بديهية خارجية واحدة: الافتراض الخارجي الوحيد هو عدم قابلية تقرير مسألة هيلبرت العاشما ( $H10C\_SAT\_undec$ )، والتي تم إثباتها بنائياً في مكتبة coq-library-undecidability.
- التحقق: تؤكد الصياغة أن مبرهنة رايس ومشكلة التوقف "مغلقة تحت السياق العالمي"، مما يعني أنها تعتمد فقط على بديهية MRDP ولا تعتمد على أي مبادئ كلاسيكية أخرى.
الابتكار في بناء الشاهد: يعتمد نهج "الشاهد المزدوج" على تشفير مسألة القرار في الفرق العلاقي بين برنامجين بدلاً من تقسيم الحالات لبرنامج واحد.

4. النتائج

المبرهنة 5.1 (مبرهنة رايس): أثبت أنه لأي خاصية دلالية غير بديهية $P$ ، لا يمكن لأي برنامج أن يقرر $P$ . البرهان صالح في المنطق الحدسي.
النتيجة 6.4 (مشكلة التوقف): تم اشتقاق عدم قابلية تقرير مشكلة التوقف كإحدى النتائج المترتبة بأسطر قليلة عبر تطبيق مبرهنة رايس على خاصية "التوقف".
التحقق الرسمي: صياغة Rocq (1919 سطراً) تعمل دون أخطاء وبدون أهداف مقبولة (admitted goals). وهي تؤكد أن البرهان يظل صحيحاً ضمن نموذج حوسبي مفهرس بالخطوات.
هرم الدرجات: تقدم الورقة "درجة رايس" بناءً على درجة متعدد الحدود الديوفانتي المستخدم في الاختزال، مشيرة إلى أن الدرجة 4 كافية لاستيعاب جميع الخصائص غير القابلة للتقرير (بسبب ترميز ماتياسيفيتش).

5. الأهمية

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

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