هل يمكنك تخمين العدد الأكبر؟ الجزء 4

اختتمنا مقالنا السّابق هنا بحديثٍ مطوّلٍ عن قابليّة الحساب وآلة تورنڠ والعلاقة بينهما، لكن ما علاقةُ ذلك كلّه بالأعداد الكبيرة؟ في الحقيقية لم يوجد جوابٌ عن هذا السّؤال حتّى أيّار (مايو) من عام 1962، إذ نُشِرَ في مجلّة Bell System Technical Journal بين مقالات التّفكير التّداوليّ عن (البنى متعدّدة المنافذ) و(منافذ ضغط الموجِّه الموجيّ) مقالٌ معنونٌ بتواضعٍ (عن التّوابع غير القابلة للحساب) لمؤلّفه تيبور رادو Tibor Rado حيث قدّم الأعداد الأكبر الّتي لم يسبق أن تخيّلها شخصٌ.

كانت فكرته بسيطةً ومشابهةً لتصنيف الكلمات بحسب عدد الأحرف الّتي تحتويها، إذ نصنّف آلة تورنڠ بحسب عدد القوانين الّتي يحتويها رأس الشّريط. فبعضُ الآلات تحتوي على قاعدةٍ واحدةٍ فقط، وبعضها يحتوي على اثنتين، ومنها ما يحتوي على ثلاثٍ وهكذا دواليك. وكما يوجد عددٌ منتهٍ من الكلمات المختلفة المحتوية N حرفًا من أجل كلّ عددٍ ثابتٍ صحيحٍ N، يوجد عددٌ منتهٍ من آلات تورنڠ المختلفة المحتوية N قانونًا. ومن هذه الآلات ما يتوقّف ومنها ما يعمل إلى الأبد إذا ما شُغّل على شريطٍ فارغٍ. وعن تلك الّتي تتوقّف سأل رادو: ما أكبرُ عدد خطواتٍ تُجريه أيُّ آلةِ تورنڠ قبل أن تتوقّف؟ في الواقع، كان سؤال رادو الرّئيسيّ عن أكبر عددٍ من الرّموز الّتي تستطيعُ أيُّ آلةٍ أن تكتبها على الشّريط قبل أن تتوقّف، لكنّ العدد الأكبر من الخطوات الّذي يدعوه رادو S(n) يتمتّع بالخصائص الأساسيّة نفسها، ومناقشته أسهل من مناقشة ما سأل عنه رادو مباشرةً.

سمّاه رادو عدد القندس المنشغل Busy Beaver النّونيّ. تصوّرَ رادو أنّ كلّ آلة تورنڠ قندسٌ يتحرّك بنشاطٍ على طول الشّريط تارةً يكتب رموزًا وتارةً يمحو رموزًا. ويَكمُنُ التّحدي هنا في إيجاد القندس الأنشط أو الأشدّ انشغالًا بين القنادس ذوي N قاعدةً تمامًا، شرطَ ألّا يكون منشغلًا على نحوٍ غير منتهٍ. لنفترض الآنَ أنّنا نعرف عددَ القندسِ المنشغلِ النّونيَّ الذي نرمّزه BB(N)، ثُمّ لِنَرَ ما إذا كانت آلة تورنڠ المحتويةُ N قانونًا ستتوقّف على شريطٍ فارغٍ. كلّ ما علينا فعله الآنَ تشغيلُ الآلة؛ إن توقّفتْ فهذا جيّدٌ، لكن إن لم تتوقّف بعد BB(N) خطوةً سنعرف أنّها لن تتوقّف أبدًا، ذلك بأنّ BB(N) هو أكبرُ عدد خطواتٍ ستجريه آلة تورنڠ قبل التّوقُّف. فمثلًا لو علمنا أنّ الفانين جميعَهم يموتون دون بلوغ سنِّ المئتين، لاستطعنا استنتاجَ أنّ زيدًا خالدٌ لا يموت إذا ما بلغ المئتين. إِذَنْ لا يمكن لأيّ آلة تورنڠ أن تسجّل أعداد القنادس المنشغلة، لأنّها لو استطاعتْ فعلَ ذلك لكان بإمكانها حلّ مسألة التّوقّف.

لكن إليكم المزيد؛ لنفترض أنّنا نستطيع تسمية عددٍ أكبرَ من عدد القندس المنشغل النّونيّ BB(N)، ولنسمِّه D نسبةً إلى السّدّ Dam الّذي سيكون سقفًا للقندس المنشغل تحته. كونَ D بحوزتنا، سيصبح حساب BB(N) سهلًا، إذ كلّ ماعلينا فعله محاكاة آلات تورنڠ المحتوية N قاعدةً جميعِها؛ الآلات الّتي لا تتوقّف بعدَ D خطوةً هي القنادس الّتي تخترق السّدّ، ونعلم أنّها لن تتوقّف أبدًا. وهكذا نحددّ أيّ الآلات تتوقّف، وبمعرفة عدد الخطوات الّتي تجريها كلٌّ منها قبل أن تتوقّف نستطيع معرفة أكبر هذه الأعداد حاصلين بذلك على BB(N).

تشكّل أعداد القنادس المنشغلة متتاليةً عدديّةً حدودُها BB(1)، BB(2)، BB(3) وهكذا. تتزايد هذه المتتالية تزايدًا أسرعَ من أيّ متتاليةٍ قابلةٍ للحساب، أسرعَ من الأعداد الأسّيّة والأعداد الأسّيّة المكدَّسة وحتّى متتاليةِ آكرمن، لأنّه لو استطاعت آلة تورنڠ أن تحسب متتاليةً تتزايد تزايدًا أسرع من تزايد متتالية القنادس المنشغلة لاستطاعت استخدام هذه المتتالية لتحصل على جميع الأعداد D، ولاستطاعت باستخدام هذه السّدود أن تسرد حدود متتالية القنادس المنشغلة، ما نعلم مسبقًا أنّه مستحيلٌ. متتالية القنادس المنشغلة غير قابلةٍ للحساب لأنّها تتزايد بسرعةٍ هائلةٍ لدرجة أن لا حاسوبَ يستطيع مجاراتَها حتّى نظريًّا.

ما يعني أنْ لا حاسوبَ يستطيع عرض القنادس المنشغلة جميعها واحدًا تلوَ الآخر، لكنّ ذلك لا يعني بالضّرورة أنّ على القنادس جميعِها أن تبقى مجهولةً إلى الأبد، وفي الحقيقة، منذ أن نشر رادو ورقته العلميّة أصبح العثور على حدود هذه المتتالية هوايةً لعلماء الحاسوب. من السّهل التّحقّق من أنّ BB(1) عددَ القندس المنشغل الأوّل هو العدد واحدٌ، لأنّه إن احتوت آلة تورنڠ على قاعدةٍ واحدةٍ ولم تتوقّف بعد الخطوة الأولى، فستستمرّ بالتّحرّك على الشّريط إلى ما لا نهاية، إذ لا مجالَ لسلوكٍ أعقدَ. وبوجود قاعدتين يصبح الأمر أعقد قليلًا، لكن بقليلٍ من العمل الدّؤوب نستطيع أن نتأكّد من أنّ BB(2)=6. ماذا عن القندس المنشغل الثّالث؟ في عام 1965 أثبت رادو وشين لين Shen Lin أنّ BB(3)=21، وقد كانت مهمّةً شاقّةً تطلّبت تحليلًا بشريًّا لآلاتٍ عدّةٍ للتّأكّد من أنّها لا تتوقّف، لأنّه - كما نعلم - لا خوارزميّةَ محدّدةً لسرد أعداد القنادس المنشغلة. وفي عام 1983 أثبت آلن بريدي Allan Brady أنّ BB(4)=107. ألم يثر شيءٌ من ذلك اهتمامكم بعد؟ حسنٌ، كما هو الحال في متتالية آكرمن، عليكم ألّا تنخدعوا بالأعداد الأولى.

في عام 1984 كرّس إي كي دودني A. K. Dewdney عمودًا في مجلّة Scientific American للقنادس المنشغلة، ما ألهم الرّياضيّ الهاوي جورج يوينغ George Uhing بناءَ جهازٍ مخصَّصٍ لمحاكاة آلة تورنڠ. استطاع الجهاز الّذي لم تبلغ كلفته 100 دولارٍ أن يجد آلةً تحتوي على خمسة قوانين تستطيع أن تعمل حتّى 2,133,492 خطوةً قبل أن تتوقّف، وبذلك عُرِف أنّ BB(5) يجب أن يساوي هذا العدد على الأقل، ثُمّ في عام 1989 اكتشف هاينر ماركسن Heiner Marxen ويورڠن بونتروك Jürgen Buntrock أنّ BB(5) يساوي 47,176,870 على الأقلّ، وحتّى هذا اليوم لم تٌحدَّد قيمة BB(5) بدقّةٍ علمًا أنّه قد يكون أكبرَ من هذين التّوقّعَينِ بكثيرٍ. أمّا BB(6) فقد سجّل ماركسن وبونتروك رقمًا قياسيًّا آخر عامِ 1997 بإثبات أنّه يساوي 8,690,333,381,690,951 على الأقلّ. بالرّغم من أنّه إنجازٌ كبيرٌ، ما زال ماريكسن وبونتروك وصيّادو القنادس المنشغلة الآخرون يخوضون في أمواج المجهول لا غير. قد لا تصل البشريّة أبدًا لقيمة BB(6)، فما بالكم بالقندس السّابع BB(7) وما يليه؟!

في الحقيقية، ما نزال إلى الآن غيرَ قادرين على شرح طريقة عمل آلات تورنڠ المحتوية على خمسِ قواعدَ أو ستٍّ بمصطلحاتٍ بشريّةٍ. هناك طريقةٌ واحدةٌ لفهم ذلك: حتّى آلات تورنڠ الصّغيرة تستطيع أن ترمّز مسائلَ رياضيّةً عميقةً. لنأخذ حدسيّة ڠولدبخ Goldbach Conjecture مثالًا، تنصّ الحدسيّة على أنّ كلّ عددٍ زوجيّ أكبرَ من العدد 2 يمكن كتابته على شكل مجموع عددين أوّليَّين، مثلًا 10=7+3 و18=13+5. بقيت هذه الحدسيّة مستعصيةً على الإثبات منذ عام 1742. لكن مع ذلك نستطيع تصميم آلة تورنڠ محتويةً على 100 قانونٍ مثلًا، تختبر كلّ عددٍ زوجيّ لتعرف ما إذا كان مجموع عددين أوّليَّين، وتتوقّف عندما تجد عددًا ينقض الحدسيّة. وهكذا بمعرفة قيمة BB(100) نستطيع أن نشغّل هذه الآلة BB(100) خطوةً، إن توقّفت نكون قد أثبتنا عدم صحّة الحدسيّة من أجل كلّ الأعداد الزّوجيّة، وإن لم تتوقّف علمنا أنّها لن تتوقّف أبدًا، ما يعني أنّها لن تجد عددًا ينقض الحدسيّة، وبذلك نكون قد أثبتنا صحّة الحدسيّة. لسنا بحاجة لحدٍّ أكبر من BB(100) من حدود المتتالية لحلّ المعضلة.

لكن - كما أكَّد رادو - حتّى وإن لم نستطع معرفة قِيَمَ أعداد القنادس المنشغلة، فإنّها معرّفةٌ رياضيًّا تعريفًا واضحًا كاملًا. وفي مسابقة العدد الأكبر تكاد كتابة شيءٍ مشابهٍ للتّرميز أدناه أن تضمن الفوز:

BB(11111)—Busy Beaver shift #—1, 6, 21, etc

إذ إن لم يكنِ الخصم على درايةٍ بآلة تورنڠ أو ما يشبهها، وإنّما على درايةٍ بأعداد آكرمن فحسبُ، فالفوز حليف صاحب التّرميز أعلاه حتّى وإن كان للخصم من الزّمن لكتابة عدده عمر الكون كاملًا. إذ إنّ مفتاح الفوز في مسابقة العدد الأكبرِ هو استخدام نموذجٍ قويٍّ، ونظريّة تورنڠ للحسابِ قويّةٌ فعلًا.

لكنْ، ماذا لو كان الخصم على درايةٍ بآلة تورنڠ؟ هل من نظامٍ لترميز للأعداد الكبيرة أقوى من القنادس المنشغلة؟ تابعونا في الجزء القادم.

المصادر :

1- هنا