تخيل أنك تحاول فرز كومة ضخمة من الحروف. بعض الحروف بسيطة، مثل "A" أو "B"، ويمكنك فرزها بسرعة بمجرد النظر إلى الحروف الأولى. أما غيرها فمراوغة، مثل دمى الماتريوشكا الروسية المتداخلة: في كل مرة ترى فيها حرف "نداء" (Call)، يجب أن تنتظر حرف "عودة" (Return) مطابق له لاحقاً في الكومة لتعرف ما يجب فعله. في عالم علوم الحاسوب، تُسمى هذه لغات الآلات ذات الدفع اليدوي المرئي (Visibly Pushdown Languages - VPLs). هذه هي القواعد التي تحكم كيفية تعامل الحواسيب مع أشياء مثل مطابقة الأقواس في البرمجيات أو موازنة الوسوم (tags) في صفحات الويب.

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

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

1. الفئة السهلة: وهي بالتأكيد ضمن AC0 (سريعة جداً).
2. الفئة الصعبة: وهي بالتأكيد ليست ضمن AC0 (تتطلب دوائر معقدة).
3. فئة الغموض: وهي "المتوسطة".

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

قصة الدمى المتداخلة

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

• حروف النداء (Call letters): هي مثل "بدء فصل جديد". يقوم أمين المكتبة بوضع علامة على الرف.
• حروف العودة (Return letters): هي مثل "إنهاء الفصل". يقوم أمين المكتبة بالتحقق من الرف ليرى ما إذا كانت العلامة مطابقة.
• الحروف الداخلية (Internal letters): هي مجرد نص داخل الفصل؛ ولا تغير حالة المكدس.

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

الفئات الثلاث

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

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

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

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

• هذه القواعد هي شبه خالية من العد (Quasi-Counterfree): أي أنها لا تملك حلقات تكرارية بسيطة تجعل التنبؤ بها سهلاً.
• وهي متزامنة الطول ضعيفاً ولكن ليست متزامنة الطول (Weakly Length-Synchronous but not Length-Synchronous): وهذا تعبير معقد يعني أن أجزاء "الدخول" و"الخروج" من القاعدة مرتبطة ببعضها، لكن ليس بطريقة تناسب مثالية (مثل 1 إلى 1).

لقد أثبت المؤلفان أنه إذا وقعت قاعدتك في هذه "الفئة المتوسطة"، فيمكن لخوارثميتهم تحديد نوع القاعدة المتوسطة بدقة. بل يمكنهم أيضاً إظك لك مثالاً بسيطاً ومحدداً لقاعدة متوسطة (مثل قواعد نحوية محددة تبدأ بالرمز $S$ والتي يمكن أن تتحول إلى $ack-1Sb1$أو$acl-1Sb2$) تكون مكافئة رياضياً لقاعدتك المعقدة.

التخمين الكبير

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

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

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

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

أظهر المؤلفان أيضاً أن طريقتهم تعمل مع نوع أبسط وأكثر تحديداً من القواعد يسمى لغات العد المرئي (Visibly Counter Languages) (وهي تشبه VPLs ولكن مع نوع واحد فقط من علامات المكدس). وهذا يؤكد ويحسن العمل السابق لعلماء آخرين (Krebs et al.)، مما يثبت أن طريقتهم الجديدة هي أداة عامة قوية.

الخلا الخلاصة

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

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

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