🔢 mathematics

A Linear-Size Block-Partition Fibonacci Encoding for Gödel Numbering

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

المؤلفون الأصليون: Zoltán Sóstai

نُشر 2026-03-27

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

CC BY 4.0

المؤلفون الأصليون: Zoltán Sóstai

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

تخيل أن لديك مكتبة لا نهائية من الأرقام، ولكنك تريد تحويل أي جملة تكتبها (مثل "Hello World" أو معادلة رياضية معقدة) إلى رقم واحد فريد. هذا ما يسمى بـ ترقيم غودل (Gödel numbering)، تيمناً بعالم المنطق الشهير الذي أدرك أنه إذا استطعت تحويل الكلمات إلى أرقام، يمكنك استخدام الرياضيات لدراسة المنطق نفسه.

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

تقدم هذه الورقة طريقة جديدة، أكثر ذكاءً بكثير، باستخدام أرقام فيبوناتشي (Fibonacci numbers) (وهي المتتالية حيث كل رقم هو مجموع الرقمين السابقين له: 1، 1، 2، 3، 5، 8، 13...).

إليك تفصيل بسيط لابتكار المؤلف:

1. المشكلة في "الطريقة القديمة" (طريقة روسكو)

يقارن المؤلف طريقته الجديدة بتقنية قديمة لباحث يدعى روسكو.

التشبيه: طريقة روسكو تشبه أخذ صندوقين ووضعهما داخل صندوق أكبر، ثم أخذ ذلك الصندوق الأكبر ووضعه داخل صندوق أكبر منه، وهكذا.
النتيجة: في كل مرة تضيف فيها حرفاً جديداً إلى جملتك، يتعين عليك "تداخل" الشيء بأكمله داخل حاوية جديدة وضخمة. إذا كانت جملتك تتكون من 10 أحرف، فإن الرقم الذي ستحصل عليه سيكون أكبر بنحو $2^{10}$ مما ينبغي أن يكون. وإذا كانت تحتوي على 50 حرفاً، فسيكون الرقم ضخماً لدرجة أنه سيستغرق كتابته عدداً من الذرات يفوق عدد الذرات الموجودة في الكون. هذا هو الانفجار الأسي.

2. الحل الجديد: "تقسيم الكتل" (Block Partitioning)

طريقة المؤلف الجديدة تشبه تنظيم فندق بدلاً من تداخل الصناديق.

تشبيه الفندق:
- تخيل فندقاً ذا طوابق لا نهائية.
- بدلاً من وضع كل ضيف في غرفة واحدة ضخمة، سنقسم الفندق إلى كتل (blocks) من الغرف.
- الكتلة 1 مخصصة للحرف الأول من جملتك.
- الكتلة 2 مخصصة للحرف الثاني.
- الكتلة 3 مخصصة للحرف الثالث.
- الفجوة السحرية: بين الكتلة 1 والكتلة 2، نترك فجوة (ممر فارغ). وبين الكتلة 2 والكتلة 3، نترك فجوة أخرى.
كيف يعمل الأمر:
- إذا كان حرفك الأول هو "A"، تختار غرفة محددة في الكتلة 1.
- إذا كان حرفك الثاني هو "B"، تختار غرفة محددة في الكتلة 2.
- وبسبب الفجوات بين الكتل، أنت تضمن أن الغرفة التي اخترتها لـ "A" والغرفة التي اخترتها لـ "B" لن تكونا أبداً متجاورتين.
لماذا تهم الفجوة:
- في عالم أرقام فيبوناتشي، هناك قاعدة خاصة (مبرهنة زيكندورف) تقول: إذا اخترت أرقاماً لا تكون متجاورة أبداً في المتتالية، فهناك طريقة واحدة فقط لجمعها للوصول إلى إجمالي معين.
- ولأن "الفجوات" الخاصة بنا تضمن أن الغرف ليست جيرانًا، فإن مجموع أرقام الغرف (أرقام فيبوناتشي) يخلق رمزاً فريداً. لا يمكن لأي جملتين مختلفتين أن تؤديا أبداً إلى نفس الرقم الإجمالي.

3. النتيجة: النمو الخطي

هذا هو الفوز الكبير.

الطريقة القديمة (روسكو): إضافة حرف واحد يضاعف حجم الرقم. (نمو أسي).
الطريـقة الجديدة (تقسيم الكتل): إضافة حرف واحد يضيف فقط مقداراً ثابتاً وصغيراً من "المساحة" إلى الرقم.
- إذا كانت كلمة من حرف واحد تنتج رقماً من خانتين، فإن كلمة من 10 أحرف تنتج رقماً من 20 خانة.
- إذا كانت كلمة من 100 حرف تنتج رقماً من 200 خانة.
- إنها تنمو خطياً. الأمر يشبه إضافة طوبة واحدة إلى جدار مقابل كل حرف جديد، بدلاً من إعادة بناء الجدار بالكامل ليكون ضعف الحجم.

4. لماذا هذا مهم

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

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "ترميز فيبوناتشي ذو تقسيم الكتل ذي الحجم الخطي لترقيم غودل" للباحث زولتان سوستاي.

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

تتناول الورقة مشكلة ترقيم غودل (Gödel numbering): وهي عملية الربط المتباين (injective mapping) للسلاسل المنتهية (الأجسام النحوية مثل الصيغ أو البراهين) فوق أبجدية ثابتة $\Sigma$ إلى الأعداد الطبيعية.

السياق: تعتمد مبرهنات عدم الاكتمال لغودل على مثل هذه الترميزات. الطرق التقليدية، مثل ترميز القوى الأولية ( $2^{a_1+1} \cdot 3^{a_2+1} \cdots$ )، تنتج أعداداً ذات نمو فائق الخطية (غالباً مئات الأرقام لسلاسل قصيرة)، مما يجعلها غير عملية حوسبياً.
البدائل الموجودة: اقترح روسكو (2025) استخدام تمثيلات زيكندورف (مجموع أعداد فيبوناتشي غير المتتالية) باستخدام دالة "ازدواج خالي من الحمل" (carryless pairing). ومع ذلك، تحدد الورقة خللاً جوهرياً في التطبيق القياسي لهذه الطريقة: التداخل جهة اليمين (right-nesting) للازدواجات الثنائية يؤدي إلى نمو أسي في عدد الأرقام ( $\Theta(2^m)$ )، وهو أمر غير فعال.
الهدف: بناء ترميز يكون متبايناً (injective)، ويسمح باستعادة الطول، ويحقق نمواً خطياً في عدد الأرقام ( $\Theta(m)$ ) بالنسبة لطول السلسلة $m$ ، مما يطابق الحد الأدنى للمعلومات نظرياً حتى معامل ثابت.

2. المنهجية: ترميز تقسيم الكتل

يقترح المؤلف بناءً مبتكراً يعتمد على تقسيم متتالية فيبوناتشي إلى كتل متجاورة، تفصل بينها فجوات.

التعريفات الأساسية

الأبجدية: أبجدية منتهية $\Sigma = \{\sigma_0, \dots, \sigma_{k-1}\}$ مع رموز الأشكال $c \in \{0, \dots, k-1\}$ .
حجم الكتلة: يُعرف بـ $\beta = k + 1$ .
تقسيم الكتل: يتم تقسيم مؤشرات متتالية فيبوناتشي إلى كتل $B_i$ $B_{i}$ لكل موضع سلسلة $i \ge 0$ $i \geq 0$ .
- تحتوي الكتلة $B_i$ على المؤشرات: $\{2 + i\beta, 2 + i\beta + 1, \dots, 2 + i\beta + (k-1)\}$ .
- الفجوة: يُترك المؤشر $2 + i\beta + k$ غير مستخدم. تضمن هذه الفجوة أن أكبر مؤشر في الكتلة $B_i$ وأصغر مؤشر في $B_{i+1}$ يفصل بينهما مؤشران على الأقل.
قاعدة الترميز: لسلسلة $s = s_1 \dots s_m$ ذات رموز الأشكال $c_1, \dots, c_m$ :
$\ulcorner s \urcorner = \sum_{i=0}^{m-1} F_{2 + i\beta + c_{i+1}}$
كل رمز في الموضع $i$ يختار بالضبط رقماً واحداً من متتالية فيبوناتشي من كتلته المخصصة $B_i$ .

الأساس النظري

يعتمد الترميز على مبرهنة زيكندورف (Zeckendorf's Theorem)، والتي تنص على أن كل عدد موجب له تمثيل فريد كمجموع لأعداد فيبوناتشي غير متتالية.

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

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

بناء ذي حجم خطي: قدمت الورقة أول ترميز قائم على زيكندورف يحقق نمواً خطياً في عدد الأرقام ( $\Theta(m)$ ) لترميز السلاسل، متجنبة التضخم الأسي الناتج عن طرق الازدواج المتداخل.
التبيان والقدرة على فك التشفير:
- التبيان (Injectivity): تم إثباته عبر تفرد تمثيلات زيكندورف. السلاسل المختلفة ترتبط بأعداد مختلفة.
- استعادة الطول: يمكن استعادة طول السلسلة الأصلية $m$ مباشرة من الكود $n$ عن طريق عد المصطلحات في دعم زيكندورف الخاص به ( $|Z(n)| = m$ ).
- فك التشفير: يمكن إعادة بناء السلسلة باستخدام خوارزمية جشعة (greedy algorithm) من خلال تحديد مؤشر الكتلة ورمز الشكل لكل مصطلح في المجموع.
تحليل التعقيد:
- طول الكود: ينمو عدد الأرقام كـ $\Theta(m)$ . على وجه التحديد، بالنسبة لأبجدية مكونة من 10 رموز، يبلغ الهيكل الإضافي حوالي 2.3 رقماً لكل رمز.
- المثالية: البناء مثالي تقاربياً، حيث يطابق الحد الأدنى للمعلومات نظرياً ( $\Omega(m)$ ) حتى معامل ثابت.
نقد الازدواج المتداخل: تثبت الورقة بصرامة أن التطبيق المتداخل جهة اليمين لعملية ازدواج روسكو الثنائية الخالية من الحمل يؤدي إلى نمو أسي $\Theta(2^m)$ في عدد الأرقام، مما يوضح سبب تفوق نهج تقسيم الكتل.

4. النتائج

المبرهنة 5.1 (طول الكود الخطي): لأي سلسلة بطول $m$ ، يكون عدد الأرقام في الحالة الأسوأ هو $\Theta(m)$ .
المبرهنة 5.2 (المثالية التقاربية): الترميز مثالي حتى معامل ثابت. بالنسبة لـ $k=10$ ، المعامل الثابت هو تقريباً 2.3 مقارنة بالحد الأدنى النظري.
الفرضية 5.3 (التضخم الأسي): الازدواج الخالي من الحمل المتداخل جهة اليمين ينتج أكواداً بعدد أرقام $\Theta(2^m)$ $Θ (2^{m})$ .
- مثال: سلسلة بطول 5 عند ترميزها عبر تقسيم الكتل تستخدم حداً أقصى لمؤشر فيبوناتشي قدره 55. بينما نفس السلسلة عند ترميزها عبر الازدواج المتداخل تستخدم مؤشراً قدره 245، مما يوضح التباعد السريع.
المقارنة: توفر الورقة جدولاً يقارن بين أربع طرق:
- القوى الأولية (غودل): نمو فائق الخطية.
- النظام الموضعي ذو القاعدة $k$ : خطي (معامل مثالي).
- الازدواج الخالي من الحمل المتداخل جهة اليمين (روسكو): أسي ( $\Theta(2^m)$ ).
- تقسيم الكتل (هذه الورقة): خطي ( $\Theta(m)$ ).

5. الأهمية

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

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