مقدمة: لغز السلاسل الثلاث ذات المليون بت — النقطة العمياء في نظرية شانون

تخيّل أن أمامك ثلاث سلاسل ثنائية يبلغ طول كل واحدة منها بالضبط $1,000,000$ بت:

• السلسلة الأولى $S_1$ هي تكرار النمط 01 خمسمئة ألف مرة: 01010101...01.
• السلسلة الثانية $S_2$ تمثل أول مليون خانة ثنائية بعد الفاصلة للثابت الرياضي $\pi$: 1100100100001111110110....
• السلسلة الثالثة $S_3$ هي المتتالية الناتجة عن رمي قطعة نقد متوازنة مليون مرة متتالية (صورة = 1، كتابة = 0).

أيّ هذه السلاسل الثلاث يحتوي على «معلومات» أكثر؟ وأيّها أكثر «تعقيداً»؟ وأيّها هو «العشوائي» حقاً؟ إذا بحثنا عن الإجابة في نظرية المعلومات الكلاسيكية لكلود شانون (1948)، فسنصطدم بمعضلة غير متوقعة: إنتروبيا شانون $H(X) = -\sum P(x)\log_2 P(x)$ تقيس متوسط عدم اليقين في توزيع احتمالي (مجموعة إحصائية Ensemble)، لكنها عاجزة تماماً عن قياس التعقيد الذاتي لكائن فردي محدد $x$ بحد ذاته! ففي نموذج رمي العملة المتوازنة، تتساوى احتمالية ظهور السلسلة المنتظمة تماماً $S_1$ مع احتمالية ظهور السلسلة الفوضوية $S_3$ وتبلغ $2^{-1,000,000}$ لكلتيهما؛ أما الثابت الحتمي $\pi$ ($S_2$) فتوزيعه الاحتمالي نقطي ذو إنتروبيا صفرية ($H=0$)، رغم أن تكرارات الأصفار والآحاد فيه تجتاز جميع الاختبارات الإحصائية للعشوائية الكاذبة!

لوضع أساس رياضي صارم لتعقيد وعشوائية الكائن الفردي، أسس كل من راي سولومونوف (1960) وأندريه كولموغوروف (1965) وغريغوري تشايتين (1966) بشكل مستقل نظرية المعلومات الخوارزمية (Algorithmic Information Theory, AIT). وكانت بصيرتهم المشتركة ثورية: إن التعقيد الحقيقي لأي كائن لا يُقاس بعدد رموزه الظاهرية، بل بطول «أقصر برنامج حاسوبي» قادر على توليده!

  flowchart TD
    S1["String S1: 010101...01 (1M bits)"] -->|"Short Loop Program"| K1["K(S1) = O(log n) bits (Highly Compressible)"]
    S2["String S2: Binary Digits of Pi (1M bits)"] -->|"Spigot Algorithm"| K2["K(S2) = O(log n) bits (Deterministic Law)"]
    S3["String S3: Fair Coin Flips (1M bits)"] -->|"No Pattern / Hardcoded"| K3["K(S3) >= n - O(1) bits (Algorithmically Random)"]

1. تعقيد كولموغوروف $K(x)$ ومبرهنة اللاتغير لآلة تورينغ الكونية

بالنسبة لآلة تورينغ كونية $U$ (أو أي لغة برمجة كاملة بتعريف تورينغ مثل C أو Python)، يُعرّف تعقيد كولموغوروف $K_U(x)$ لسلسلة ثنائية $x \in \{0,1\}^*$ بأنه طول البتات $|p|$ لأقصر برنامج $p$ يطبع السلسلة $x$ ثم يتوقف عند تشغيله على الآلة $U$. ولضمان تقارب مجموع الاحتمالات (متباينة كرافت $\sum 2^{-|p|} \le 1$)، تعتمد النظرية الحديثة التعقيد الخالي من البوادئ (تعقيد ليفين-تشايتين) $K(x)$، حيث لا يكون أي برنامج صالح بادئة لبرنامج صالح آخر.

عندما نعيد النظر إلى سلاسل المليون بت الثلاث عبر عدسة $K(x)$، ينقشع الضباب فوراً:

• بالنسبة للسلسلة $S_1$، يكفي البرنامج القصير جداً print("01" * 500000). ولأننا نحتاج فقط إلى ترميز عداد الحلقة $n/2$ ثنائياً، فإن $K(S_1) = O(\log_2 n) pprox 20$ بت فقط: إنها سلسلة بسيطة للغاية خوارزمياً.
• بالنسبة للسلسلة $S_2$ (أول $n$ بت من $\pi$)، فرغم أنها تبدو كضجيج عشوائي، فإن برنامجاً صغيراً من بضع مئات من البايتات ينفذ صيغة ماشين أو خوارزمية BBP يحسب $S_2$ بدقة تامة. وبالتالي فإن $K(S_2) = O(\log_2 n)$ أيضاً! وهذا يكشف حقيقة عميقة في فلسفة العلوم: القانون الطبيعي ليس سوى ضغط خوارزمي فائق لبيانات الرصد التجريبية.
• أما السلسلة $S_3$ الناتجة عن رمي العملة الحقيقي، فلا يوجد فيها أي نمط خفي يسمح باختزالها. إن أقصر برنامج قادر على طباعة $S_3$ مضطر لتضمين المليون بت حرفياً داخله (print("1011001..."))، ومن ثم فإن $K(S_3) pprox n + O(1) pprox 1,000,000$ بت!

قد يتساءل القارئ: ألا يعتمد $K_U(x)$ بشكل تعسفي على لغة البرمجة $U$ المختارة؟ تثبت مبرهنة اللاتغير لكولموغوروف (Invariance Theorem) عكس ذلك: لأي آلتين كونيتين $U_1$ و$U_2$، يوجد ثابت $c_{12}$ يعتمد فقط على $U_1$ و$U_2$ (ولا يعتمد إطلاقاً على السلسلة $x$) بحيث يتحقق $|K_{U_1}(x) - K_{U_2}(x)| \le c_{12}$ لكل $x$. البرهان بديهي للغاية: الثابت $c_{12}$ ليس سوى الحجم الثابت بالبتات لبرنامج مفسّر (Interpreter) مكتوب بلغة $U_1$ يحاكي عمل $U_2$! وعندما يكبر حجم البيانات $n o \infty$، يصبح هذا العبء الثابت مهملاً تماماً.

2. جوهر العشوائية: مبدأ برج الحمام، عدم القابلية للضغط، وعشوائية مارتن-لوف

قبل كولموغوروف، عجزت نظرية الاحتمالات عن تفسير لماذا لا تُعد السلسلة 0000000000 عشوائية بينما تبدو 0110100110 عشوائية. قدّمت نظرية المعلومات الخوارزمية أول تعريف رياضي صارم للعشوائية الفردية: العشوائية هي عدم القابلية للضغط (Incompressibility) — أي الغياب التام لأي انتظام خوارزمي!

والأدهى من ذلك أنه باستخدام مبدأ برج الحمام (Pigeonhole Principle) البسيط، يمكننا أن نبرهن في سطرين أن الأغلبية الساحقة من السلاسل الثنائية هي سلاسل عشوائية خوارزمياً (غير قابلة للضغط): يوجد بالضبط $2^n$ سلسلة ثنائية بطول $n$. كم عدد البرامج الثنائية التي يقل طولها قطعا عن $n - c$ بت؟ بجمع أعداد البرامج ذات الأطوال $0, 1, \dots, n-c-1$، نحصل على $\sum_{i=0}^{n-c-1} 2^i = 2^{n-c} - 1$ برنامجاً على الأكثر. وبما أن كل برنامج ينتج مخرجاً واحداً كحد أقصى، فإنه من بين $2^n$ سلسلة بطول $n$، هناك على الأكثر $2^{n-c} - 1$ سلسلة فقط يمكن ضغطها بأكثر من $c$ بت ($K(x) < n - c$)! بعبارة أخرى، فإن نسبة السلاسل ذات الطول $n$ القابلة للضغط بمقدار $c$ بت أو أكثر تقل قطعا عن $2^{-c}$. فإذا أخذنا $c = 20$، فإن أكثر من $99.9999\,\%$ من السلاسل لا يمكن تقصيرها حتى بمقدار $20$ بت بأي خوارزمية ممكنة! وفي عام 1966 أثبت بير مارتن-لوف أن المتتالية الثنائية اللانهائية تجتاز جميع الاختبارات الإحصائية القابلة للحساب (عشوائية مارتن-لوف) إذا وفقط إذا كانت جميع بوادئها $x_{1:n}$ غير قابلة للضغط ($K(x_{1:n}) \ge n - O(1)$).

  flowchart TD
    A["Assume Program P_K Computes K(x)"] --> B["Construct Program Q of Length L = |Q|"]
    B --> C["Q Searches Lexicographically for First String s with K(s) > L + 1000"]
    C --> D["Q Outputs s, so by Definition K(s) <= |Q| = L"]
    D --> E["Contradiction: L + 1000 < K(s) <= L (Berry Paradox / Uncomputability)"]

3. مفارقة بيري، عدم قابلية $K(x)$ للحساب، ثابت تشايتين $\Omega$، والذكاء الاصطناعي الحديث

إذا كان $K(x)$ بهذه القوة، فهل يمكننا كتابة برنامج ضغط مثالي يستقبل أي سلسلة $x$ ويحسب قيمة $K(x)$ بدقة؟ الجواب هو الاستحالة المطلقة: الدالة $K(x)$ غير قابلة للحساب (Uncomputable)!

ينبع هذا القيد العميق من مفارقة بيري (Berry’s Paradox) الشهيرة («أصغر عدد صحيح موجب لا يمكن تعريفه بأقل من عشرين كلمة» — وهي جملة عرّفته في إحدى عشرة كلمة فقط!). صاغها غريغوري تشايتين رياضياً كالتالي: لنفترض وجود دالة فرعية ComputeK(x) بطول ثابت $L$ بت تحسب $K(x)$. نبني عندئذٍ برنامجاً رئيسياً $Q$ يمر على جميع السلاسل $s$ بترتيب معجمي، ويستدعي ComputeK(s)، ويطبع أول سلسلة $s^*$ تحقق $K(s^*) > L + 10000$ ثم يتوقف. إن الطول الكلي للبرنامج $Q$ هو $L + O(1)$ بت فقط، ومع ذلك نجح في طباعة $s^*$! وبحسب تعريف $K(s^*)$ كأقصر برنامج يولّد $s^*$، يجب أن يكون $K(s^*) \le |Q| < L + 10000$، وهو تناقض صريح مع الشرط $K(s^*) > L + 10000$! ومن هنا تنتج مبرهنة عدم الاكتمال لتشايتين: لا يمكن لأي نظام بديهيات صوري ذي تعقيد $C$ بت أن يثبت أن سلسلة محددة تحقق $K(x) > C + O(1)$.

كما جمع تشايتين احتمالات التوقف لآلة تورينغ الكونية الخالية من البوادئ في عدد حقيقي أسطوري هو ثابت أوميغا $\Omega = \sum_{U(p) ext{ يتوقف}} 2^{-|p|}$. ورغم أن $\Omega \in (0,1)$ عدد محدد بدقة، فإنه غير قابل للحساب إطلاقاً وعشوائي خوارزمياً لأقصى درجة ($K(\Omega_{1:n}) \ge n - O(1)$): فمعرفة أول $n$ بت من $\Omega$ تكافئ حل مسألة التوقف لتورينغ لجميع البرامج حتى طول $n$!

في الهندسة الحديثة والذكاء الاصطناعي، تقود الحدود العليا القابلة للحساب للدالة $K(x)$ أهم التطبيقات:

1. الجسر مع إنتروبيا شانون: للعمليات العشوائية المستقرة الإرغودية، يتقارب التوقع $ rac{1}{n}\mathbb{E}[K(X_{1:n})]$ إلى معدل إنتروبيا شانون $H(X)$.
2. استقراء سولومونوف الكوني وأقصر طول وصف (MDL): تتم صياغة شفرة أوكام رياضياً عبر التوزيع المسبق الكوني $P_M(x) \propto 2^{-K(x)}$.
3. مسافة الضغط المعيّرة (NCD): بتقريب $K(x)$ عبر ضواغط حقيقية (zstd, lzma, gzip) في الصيغة $ ext{NCD}(x,y) = rac{C(xy) - \min(C(x),C(y))}{\max(C(x),C(y))}$، يمكن بناء أشجار التطور الجيني وتصنيف البرمجيات الخبيثة دون هندسة ميزات يدوية.
4. نماذج اللغة الكبيرة (LLMs): الضغط هو الذكاء: كما أوضح ماركوس هوتر (جائزة Hutter) وإيليا سوتسكيفر، فإن تقليل خسارة الإنتروبيا المتقاطعة $-\sum \log_2 P_ heta(x_t \mid x_{البحث عن أقصر ضغط غير فاقد لبيانات النصوص البشرية. ولضغط النصوص إلى أقصى حد، يضطر النموذج إلى استيعاب القواعد النحوية والاستدلال المنطقي والنموذج السببي للعالم.