إن دليل تورينج القطري هو نسخة من هذه اللعبة حيث يتم تشغيل الأسئلة من خلال قائمة لا حصر لها من الخوارزميات المحتملة، وتتساءل بشكل متكرر، “هل يمكن لهذه الخوارزمية أن تحل المشكلة التي نود أن نثبت أنها غير قابلة للحساب؟”
قال ويليامز: “إنها نوع من الأسئلة اللامتناهية”.
للفوز باللعبة، كان تورينج بحاجة إلى صياغة مشكلة حيث يكون الجواب لا لكل خوارزمية. وهذا يعني تحديد مدخل معين يجعل الخوارزمية الأولى تنتج إجابة خاطئة، ومدخلًا آخر يجعل الخوارزمية الثانية تفشل، وهكذا. لقد وجد تلك المدخلات الخاصة باستخدام خدعة مشابهة لتلك التي استخدمها كورت جودل مؤخرًا لإثبات أن التأكيدات المرجعية الذاتية مثل “هذا البيان غير قابل للإثبات” تسبب مشكلة لأسس الرياضيات.
كانت الفكرة الرئيسية هي أن كل خوارزمية (أو برنامج) يمكن تمثيلها كسلسلة من 0 و1. وهذا يعني، كما في مثال برنامج التحقق من الأخطاء، أنه يمكن للخوارزمية أن تأخذ كود خوارزمية أخرى كمدخل. من حيث المبدأ، يمكن للخوارزمية أن تأخذ الكود الخاص بها كمدخل.
من خلال هذه الرؤية، يمكننا تحديد مشكلة غير قابلة للحساب مثل تلك الموجودة في برهان تورينج: “بالنظر إلى سلسلة إدخال تمثل كود الخوارزمية، يكون الإخراج 1 إذا كانت هذه الخوارزمية تنتج 0 عندما يكون الكود الخاص بها هو الإدخال؛ وإلا، الإخراج 0.” كل خوارزمية تحاول حل هذه المشكلة ستنتج مخرجات خاطئة على مدخل واحد على الأقل، أي المدخلات المقابلة للكود الخاص بها. وهذا يعني أن هذه المشكلة الضارة لا يمكن حلها بأي خوارزمية على الإطلاق.
ما النفي لا يمكن أن تفعل
لم ينته علماء الكمبيوتر بعد من عملية التحديد القطري. في عام 1965، قام جوريس هارتمانيس وريتشارد ستيرنز بتعديل حجة تورينج لإثبات أنه ليست كل المسائل الحسابية متساوية، فبعضها أصعب في جوهره من البعض الآخر. أطلقت هذه النتيجة مجال نظرية التعقيد الحسابي، التي تدرس مدى صعوبة المشاكل الحسابية.
لكن نظرية التعقيد كشفت أيضًا عن حدود طريقة تورينج المعاكسة. في عام 1975، أثبت ثيودور بيكر، وجون جيل، وروبرت سولوفاي أن العديد من الأسئلة المفتوحة في نظرية التعقيد لا يمكن حلها أبدًا عن طريق التحديد القطري وحده. وأهم هذه المشاكل هي مشكلة P مقابل NP الشهيرة، والتي تتساءل عما إذا كانت جميع المشكلات ذات الحلول التي يمكن التحقق منها بسهولة من السهل أيضًا حلها باستخدام الخوارزمية البارعة الصحيحة.
إن النقاط العمياء للقطرية هي نتيجة مباشرة للمستوى العالي من التجريد الذي يجعلها قوية جدًا. لم يتضمن برهان تورينج أي مشكلة غير قابلة للحساب قد تنشأ أثناء الممارسة، وبدلاً من ذلك، فقد اختلق مثل هذه المشكلة بسرعة. إن البراهين القطرية الأخرى بعيدة بالمثل عن العالم الحقيقي، لذلك لا يمكنها حل الأسئلة التي تكون فيها تفاصيل العالم الحقيقي مهمة.
قال ويليامز: “إنهم يتعاملون مع العمليات الحسابية عن بعد”. “أتخيل رجلاً يتعامل مع الفيروسات ويصل إليها من خلال صندوق القفازات.”
كان فشل التحديد القطري مؤشرًا مبكرًا على أن حل مشكلة P مقابل NP سيكون رحلة طويلة. ولكن على الرغم من محدودياتها، تظل القطيعة واحدة من الأدوات الرئيسية في ترسانة منظري التعقيد. في عام 2011، استخدمها ويليامز مع مجموعة من التقنيات الأخرى لإثبات أن نموذجًا مقيدًا معينًا للحساب لا يمكنه حل بعض المشكلات الصعبة للغاية – وهي النتيجة التي استعصت على الباحثين لمدة 25 عامًا. لقد كانت بعيدة كل البعد عن حل P مقابل NP، لكنها لا تزال تمثل تقدمًا كبيرًا.
إذا كنت تريد إثبات أن شيئًا ما غير ممكن، فلا تقلل من أهمية مجرد قول لا.
القصة الأصلية أعيد طبعها بإذن من مجلة كوانتا، منشور تحريري مستقل لـ مؤسسة سيمونز وتتمثل مهمتها في تعزيز الفهم العام للعلم من خلال تغطية التطورات والاتجاهات البحثية في الرياضيات والعلوم الفيزيائية والحياة.
