🔢 mathematics

Automated conjecturing with \emph{TxGraffiti}

تقدم هذه الورقة تصميم ومبادئ جوهرية ومنهجية تعتمد على البيانات لبرنامج \emph{TxGraffiti}، وهو برنامج حاسوبي يعمل على أتمتة توليد التخمينات الرياضية — لا سيما في نظرية المخططات — مع تسليط الضوء على مساهماته في الأدبيات العلمية وتقديم واجهة ويب تفاعلية جديدة.

المؤلفون الأصليون: Randy Davila

نُشر 2026-05-12

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

CC0 1.0

المؤلفون الأصليون: Randy Davila

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

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

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

إليك كيف يعمل، مقسماً إلى خطوات بسيطة:

١. مكتبة "اللقطة" (The Snapshot Library)

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

٢. "لعبة التخمين" (ملاءمة الخط - Fitting the Line)

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

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

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

٣. مرشح "لوحة الشرف" (خوارزمية دالماتيان - The Dalmatian Heuristic)

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

لإصلاح ذلك، يستخدم TxGraffiti مرشحاً يسمى Dalmatian Heuristic. فكر فيه كأنه أمين متحف:

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

يضمن هذا أن تكون القائمة النهائية قصيرة، حادة، وتحتوي فقط على الاكتشافات الأكثر إثارة للاهتمام.

٤. من التخمين إلى البرهان

مخرجات TxGraffiti هي قائمة من التخمينات الرياضية (Conjectures). في الرياضيات، التخمين هو "تخمين ذكي" يبدو صحيحاً بناءً على الأدلة ولكنه لم يُثبت بعد.

سير العمل: ينظر عالم الرياضيات البشري إلى تخمين الحاسوب. يتحقق مما إذا كان منطقياً. ويحاول إثباته باستخدام المنطق.
النجاح: تذكر الورقة البحثية عدة أمثلة من العالم الحقيقي حيث وضع TxGraffiti تخميناً، ثم قام علماء الرياضيات لاحقاً بإثبات أنه مبرهنة (Theorem) (حقيقة مثبتة).
- مثال ١: خمن الحاسوب أنه في بعض الأشكال المنتظمة، لا يكون عدد القطع المستقلة أكبر أبداً من عدد الأزواج المتطابقة. وقد أثبت البشر أن هذا صحيح.
- مثال ٢: خمن الحاسوب وجود علاقة بين "الإجبار الصفري" (Zero Forcing - وهي طريقة معينة لتلوين الأشكال) والأشكال "خالية من المخلب" (Claw-free). وقد أثبت البشر ذلك أيضاً.

لماذا هذا الأمر مهم؟

قبل وجود أنظمة كهذه، كان على علماء الرياضيات التحديق في البيانات لسنوات للعثور على الأنماط. يقوم TxGraffiti بأتمتة جزء "رصد الأنماط". إنه لا يستبدل عالم الرياضيات البشري؛ بل يعمل بدلاً من ذلك كمنظار عالي القدرة، يمسح البيانات ليوجه الإنسان نحو أكثر القوانين واعدة في الكون.

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

ملخص تقني لـ "التخمين الآلي باستخدام TxGraffiti"

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

المنهجية
تقدم الورقة TxGraffiti (تكساس غرافيتي)، وهو نظام يعتمد على الاستدلال والتحسين يعمل على جدول لقطة (Snapshot Table) محدود ومؤرخ للكائنات الرياضية. وخلافاً لأسلافه (Graffiti و Graffiti.pc) الذين يحسبون الثوابت ديناميكياً أثناء البحث، يعامل TxGraffiti قاعدة الأدلة كأثر ثابت.

يتكون مسار التخمين من المراحل التالية:

تنسيق البيانات (جدول اللقطة):
- يتم إنشاء جدول تمثل صفوفه الكائنات (الرسوم البيانية) وتمثل أعمدته الثوابت العددية المحسوبة مسبقاً (مثل عدد الاستقلال $\alpha$ ، وعدد المطابقة $\mu$ ) والمحمولات المنطقية (Boolean predicates) (مثل "متصل"، "منتظم").
- تعطي استراتيجية التنسيق الأولوية لـ التغطية على العشوائية، وتحديداً تضمين البناءات القصوى، وشهود المساواة (الحالات الحادة)، والحالات المضادة لضمان أن يكون الجدول غنياً تشخيصياً.
توليد المرشحين عبر التحسين:
- بالنسبة لثابت مستهدف $\alpha$ ومحمول منطقي $P$ (فرضية)، يبحث النظام عن حدود تآلفية (affine bounds) من الشكل $\alpha \le mx + b$ أو $\alpha \ge mx + b$ ، حيث $x$ هو ثابت متنبئ.
- بدلاً من حصر أشجار التعبيرات المعقدة، يقوم TxGraffiti بتثبيت فئة فرضية بارامترية بسيطة (الحدود التآلفية أحادية المتغير) ويضبط المعاملات عن طريق حل البرمجة الخطية (LPs).
- برمجة الحد العلوي الخطية: تقلل إجمالي الفراغ (slack) $\sum (mx_i + b - \alpha_i)$ بشرط أن يكون $\alpha_i \le mx_i + b$ لجميع الصفوف التي تحقق $P$ .
- برمجة الحد السفلي الخطية: تعظم إجمالي الفراغ (أو تقلل الفراغ السالب) بشرط أن يكون $\alpha_i \ge mx_i + b$ .
- يدعم النظام أيضاً الحدود متعددة المتغيرات والعلاقات غير الخطية من خلال توسيع المخطط بأعمدة مشتقة (مثل $n-\mu$ ، $\Delta^2$ )، رغم أن واجهة الويب الافتراضية تعطي الأولوية للنماذج أحادية المتنبئ من أجل قابلية التفسير.
التصفية (استدلال دالماتيان الساكن - Static-Dalmatian Heuristic):
- لإدارة التكرار، يستخدم TxGraffiti استدلال دالماتيان الساكن.
- رقم اللمس (Touch Number): يُعرف بأنه عدد الكائنات في اللقطة التي تتحقق فيها المتراجحة مع المساواة (الحالات الحادة).
- منطق الاختيار: يتم فرز المرشحين حسب رقم اللمس. يُقبل المرشح كـ "ممثل" إذا كان يلمس كائناً واحداً على الأقل لم تغطه بعد المجموعات الحادة للممثلين المقبولين سابقاً. إذا كانت المجموعة الحادة للمرشح مطابقة لممثل مقبول، فإنه يُحتفظ به كـ "اسم مستعار" (صيغة نحوية مختلفة لنفس موضع المساواة). أما المرشحات التي لا تضيف أي حالات حادة جديدة فيتم استبعادها.

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

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

النتائج
توضح الورقة فعالية النظام من خلال عدة أمثلة:

توضيح سير العمل: باستخدام عدد الهيمنة الكلي $\gamma_t$ ، ولد النظام حداً $\gamma_t(G) \ge \frac{2}{3}R(G)$ للرسوم البيانية التي يكون فيها $\Delta(G) \le 3$ . وقد تم تعميم ذلك بسرعة إلى نظرية تتضمن $\Delta(G)$ باستخدام تقديرات قياسية.
الأبحاث المستحثة: تسجل الورقة العديد من النتائج في نظرية الرسوم البيانية التي نشأت كتخمينات من TxGraffiti وتم إثباتها لاحقاً:
- الاستقلال مقابل المطابقة: تم إثبات التخمين بأن $\alpha(G) \le \mu(G)$ للرسوم البيانية المنتظمة من الدرجة $r$ في [51].
- حدود القوة الصفرية (Zero Forcing): تم تخمين وإثبات عدة متباينات تربط أعداد القوة الصفرية ( $Z, Z_t, Z_+$ ) ببارامترات الهيمنة والاستقلال، بما في ذلك $Z(G) \le \beta(G)$ للرسوم الخالية من المخلب (claw-free) وحدود للرسوم التكعيبية.
- المسائل المفتوحة: حدد النظام التخمين $Z(G) \le \alpha(G) + 1$ للرسوم البيانية المتصلة ذات $\Delta \le 3$ ، وهي مسألة لا تزال مفتوحة مركزياً، رغم وجود نتائج جزئية.

الأهمية والادعاءات
تضع الورقة TxGraffiti ليس كأداة لاكتشاف النظريات العميقة بشكل مستقل، بل كـ مولد أدلة مهيكل يسهل الاستقصاء الرياضي البشري.

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

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