Additive systems for $\mathbb{Z}$ are undecidable

إليك ملخص تقني مفصل لورقة "الأنظمة الجمعية لـ $\mathbb{Z}$ غير قابلة للتقرير" (Additive systems for $\mathbb{Z}$ are undecidable) للباحث أندريه زابولوتسكي.

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

تتناول الورقة المشكلة الجوهرية المتمثلة في توصيف الأنظمة الجمعية لمجموعة الأعداد الصحيحة ($\mathbb{Z}$).

• التعريف: النظام الجمعي لمونود (monoid) $M$ هو مجموعة من المجموعات الجزئية $\mathcal{A} = \{A_0, A_1, \dots\}$ بحيث يمكن تمثيل كل عنصر $n \in M$ بشكل فريد كجمع منتهٍ $n = a_0 + a_1 + \dots$، حيث $a_i \in A_i$.
• السياق: بالنسبة للأعداد الصحيحة غير السالبة ($\mathbb{N}_0$)، يتم توصيف هذه الأنظمة بالكامل عبر مبرهنة دي بروين (de Bruijn's Theorem)، والتي تنص على أن أي نظام جمعي لـ $\mathbb{N}_0$ هو انكماش لنظام "الأرقام البريطانية" (نظام ذو قواعد متغيرة).
• الفجوة: إن المشكلة المماثلة لـ $\mathbb{Z}$ (تمثيل جميع الأعداد الصحيحة، الموجبة والسالبة، بشكل فريد) هي أصعب بكثير. وبينما توجد أمثلة محددة (مثل أنظمة الـ negabinary أو الـ balanced ternary)، لا يوجد توصيف هيكلي عام. السؤال المركزي هو: بالنظر إلى مجموعة محددة من المجموعات، هل هي نظام جمعي لـ $\mathbb{Z}$؟ (أي هل يغطي مجموعها المباشر مجموعة الأعداد الصحيحة بأكملها؟).

2. المنهجية

يستخدم المؤلف منهجية متعددة الخطوات تجمع بين التوافيق الجمعية (additive combinatorics)، والأنظمة الديناميكية، ونظرية القابلية للحساب (computability theory):

أ. تقديم المجموعات المعيارية (Canonical Collections)

لتعميم الأمثلة المعروفة (مثل أنظمة الـ negabinary والـ balanced ternary)، يعرّف المؤلف المجموعات المعيارية.

• الهيكل: مجموعة محددة بواسطة تسلسل من القواعد $(b_i)_{i \in \mathbb{N}_0}$ (حيث $b_i > 1$) وتسلسل من المجموعات $(T_i)_{i \in \mathbb{N}_0}$، حيث كل $T_i$ هو نظام بقايا كامل بمقياس $b_i$ يحتوي على الصفر.
• البناء: المجموعات في المجموعة المعيارية هي $A_i = (b_0 b_1 \dots b_{i-1}) T_i$.
• الخاصية: إن مجموع أي مجموعة معيارية يكون دائمًا "مباشرًا" (يوجد تمثيل فريد إذا وجد الجمع)، ولكنه ليس مضمونًا أن يكون "كاملًا" (أي يغطي $\mathbb{Z}$ بالكامل).

ب. الترجمة إلى الأنظمة الديناميكية

التحول المنهجي الجوهري هو ترجمة المشكلة الجمعية إلى نظام ديناميكي غير مستقل زمنياً (non-autonomous dynamical system).

• الدالة: لأي عدد صحيح $n$، يعرّف المؤلف تسلسلاً من الدوال $f_i: \mathbb{Z} \to \mathbb{Z}$:
  $$f_i(n) = \frac{n - t_i(n)}{b_i}$$
  حيث $t_i(n)$ هو العنصر الفريد في $T_i$ الذي يطابق $n \pmod{b_i}$.
• المسار (Trajectory): يقابل "التوسع" لـ $n$ المسار $n, f_0(n), f_1(f_0(n)), \dots$.
• التكافؤ: تكون المجموعة المعيارية كاملة (نظام جمعي لـ $\mathbb{Z}$) إذا وفقط إذا وصل مسار كل عدد صحيح $n \in \mathbb{Z}$ في النهاية إلى الصفر واستقر عنده.

ج. الاختزال إلى المشكلات غير القابلة للتقرير

يبني المؤلف حالات محددة من المجموعات المعيارية حيث تكافئ حالة "وصول المسار إلى الصفر" رياضياً مشكلات شهيرة غير محلولة أو غير قابلة للتقرير:

1. حدسية كولاتز (Collatz Conjecture): بناء مجموعة حيث يحاكي المسار خريطة $3n+1$.
2. مشكلة التوقف لـ Fractran: بناء مجموعة حيث يحاكي المسار تنفيذ برنامج Fractran (وهي لغة برمجة غريبة (esoteric) كاملة تورينج).

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

المبرهنة 1: التكافؤ مع حدسية كولاتز

يبني المؤلف مجموعة معيارية محددة $\mathcal{A}_C$ بحيث:

• $\mathcal{A}_C$ هي نظام جمعي لـ $\mathbb{Z}$ إذا وفقط إذا كانت حدسية كولاتز صحيحة.
• الآلية: يتم اختيار القواعد $b_i$ ومجموعات البقايا $T_i$ بحيث تعيد الدالة الديناميكية $f_i$ إنتاج دالة كولاتز ($3n+1$ للأعداد الفردية، و $n/2$ للأعداد الزوجية) بالنسبة للأعداد الصحيحة الموجبة. وتثبت البرهنة أن أي عدد صحيح يدخل في النهاية في "نظام كولاتز" للمسار.

المبرهنة 2: التكافؤ مع مشكلة التوقف الشاملة

يعرّف المؤلف مجموعات معيارية من نوع Fractran بناءً على برنامج Fractran $F$.

• النتيجة: برنامج Fractran $F$ يتوقف لجميع المدخلات إذا وفقط إذا كانت المجموعة المعيارية المقابلة $\mathcal{A}_F$ كاملة.
• الأهمية: بما أن مشكلة التوقف الشاملة لـ Fractran غير قابلة للتقرير (لا توجد خوارزمية لتحديد ما إذا كان برنامج عشوائي يتوقف على جميع المدخلات)، فإن مشكلة تحديد الاكتمال لهذه العائلة من المجموعات المعيارية هي أيضًا غير قابلة للتقرير.

الاستنتاج 2: عدم القابلية للتقرير

إن مسألة تحديد ما إذا كانت مجموعة معيارية من نوع Fractran هي نظام جمعي لـ $\mathbb{Z}$ هي مسألة غير قابلة للتقرير.

• وهذا يعني أنه لا توجد خوارزمية عامة لتحديد ما إذا كان نظام جمعي "جيد السلوك" (ذو وصف بيانات محدود) يغطي $\mathbb{Z}$.

4. الأهمية والآثار المترتبة

1. حل مشكلة مفتوحة منذ فترة طويلة: تقدم الورقة إجابة نهائية للتعقيد الحسابي للأنظمة الجمعية لـ $\mathbb{Z}$. فخلافاً لـ $\mathbb{N}_0$ التي تمتلك توصيفاً نظيفاً (مبرهنة دي برين)، أظهرت الورقة أن حالة الأعداد الصحيحة معقدة حسابياً بشكل لا يمكن تجاوزه.
2. الربط بين المجالات: تؤسس الورقة رابطاً عميقاً بين التوافيق الجمعية (التغطية ومجموعات الجمع)، والأنظمة الديناميكية (تقارب المسارات)، ونظرية القابلية للحساب (عدم القابلية للتقرير).
3. صعوبة التحقق: تشير النتائج إلى أن التحقق مما إذا كانت قواعد معينة تولد تمثيلاً فريداً لجميع الأعداد الصحيحة هو أمر بصعوبة حل حدسية كولاتز أو مشكلة التوقف. وهذا يفسر سبب عدم وجود مبرهنة توصيف عام لـ $\mathbb{Z}$ مشابهة لمبرهنة دي بروين.
4. منظور جديد للأنظمة العددية: من خلال صياغة الأنظمة العددية كمسارات ديناميكية، تقدم الورقة أداة جديدة لتحليل خصائص التقارب والتغطية للأنظمة العددية غير القياسية.

الخاتمة

يثبت زابولوتسكي أن السؤال "هل هذه المجموعة هي نظام جمعي لـ $\mathbb{Z}$؟" ليس مجرد مسألة صعبة فحسب، بل هو غير قابل للتقرير بالنسبة لعائلة طبيعية ومنتظمة من المجموعات. ومن خلال ترميز منطق حدسية كولاتز وبرامج Fractran في بنية هذه الأنظمة الجمعية، تثبت الورقة أن اكتمال هذه الأنظمة مرتبط ارتباطاً وثيقاً ببعض أصعب المشكلات في الرياضيات وعلوم الحاسوب.