السعي للعثور على أطول برنامج كمبيوتر بسيط

ولكن ما مدى صعوبة؟ في عام 1962 ، اخترع عالم الرياضيات Tibor Radó طريقة جديدة لاستكشاف هذا السؤال من خلال ما أسماه لعبة Beaver Baver. للعب ، ابدأ باختيار عدد محدد من القواعد – هذا الرقم ن. هدفك هو العثور على ن-آلة تورينج التي تدير الأطول قبل أن تتوقف في النهاية. يطلق على هذا الجهاز القندس المزدحم ، ورقم القندس المزدحم المقابل ، BB (ن) ، هو عدد الخطوات التي يتطلبه الأمر.

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

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

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

وقال شون ليجوكي ، وهو مهندس برمجيات وهنتر بيفر هنتر “تحسينات التكنولوجيا يساعد بالتأكيد”. “لكنهم يساعدون فقط حتى الآن.”

نهاية عصر

بدأ الصيادون في القندس المشغول في التقطيع في مشكلة BB (6) بشكل جدي في التسعينيات والألفينيات ، خلال مأزق في مطاردة BB (5). من بينهم شون ليغوكي ووالده ، تيري ، عالم الرياضيات التطبيقي الذي أدار برنامج البحث في ساعات العمل على أجهزة الكمبيوتر القوية في مختبر لورانس بيركلي الوطني. في عام 2007 ، وجدوا آلة تورينج من ستة حواق تحطمت الرقم القياسي لأطول وقت تشغيل: عدد الخطوات التي اتخذتها قبل التوقف لديها ما يقرب من 3000 رقم. هذا رقم هائل من خلال أي مقياس عادي. لكن ليس من الضروري أن يكتب. في الخط المكون من 12 نقطة ، ستغطي تلك الأرقام البالغ عددها 3000 رقم ورقة واحدة تقريبًا.

بعد ثلاث سنوات ، قرر طالب في العلوم الحاسوبية في طالبات جامعية سلوفاكية يدعى بافل كروبتز معالجة مطاردة BB (6) كمشروع أطروحة كبير. لقد كتب برنامج البحث الخاص به وقام بإعداده للتشغيل في الخلفية على شبكة من 30 جهاز كمبيوتر في مختبر جامعي. بعد شهر ، وجد آلة استمرت لفترة أطول بكثير من تلك التي اكتشفها Ligockis – “بطل” جديد ، في لغة الصيادين Baver Beaver.

وكتب كروبتز في تبادل الرسائل المباشر على خادم Discord Discord Bavor: “لقد كنت محظوظًا ، لأن الأشخاص في المختبر كانوا يشكون بالفعل من استخدام وحدة المعالجة المركزية الخاصة بي واضطررت إلى التوسع قليلاً”. بعد شهر آخر من البحث ، حطم سجله الخاص مع آلة كان وقت تشغيلها أكثر من 30،000 رقم – بملء حوالي 10 صفحات.