القندس المشغول

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

تتكون آلات تورنغ من شريط لا نهائي، ومجموعة من الحالات المنتهية التي تعمل كـ"كود مصدر" للبرنامج. يُعرّف إنتاج أكبر ناتج بكونه كتابة أكبر عدد من الرقم 1 على الشريط، ويُعرف التشغيل الأطول بأنه تنفيذ أكبر عدد من الخطوات قبل التوقف. تتكوّن لعبة القندس المشغول ذات n حالات من إيجاد آلة تورنغ تتوقف وتُنتج أكبر ناتج أو تعمل لأطول وقت ممكن بين جميع الآلات الممكنة ذات n حالات. تُفترض هذه الآلات بأنها تبدأ على شريطٍ فارغ، يحتوي فقط على الأصفار والآحاد (آلة تورنغ ثنائية). هدف اللعبة هو برمجة مجموعة من الانتقالات بين الحالات لتحقيق أعلى ناتج أو أطول وقت تشغيل مع ضمان توقّف الآلة في النهاية.

يُطلق على آلة تورنغ التي تفوز في لعبة القندس المشغول ذات n حالات اسم قندس مشغول-إن ، أو ببساطة "قندس مشغول"، وتُرمز إليها بـ بي بي-إن. وفقًا للتعريف، إما أن تُحقق هذه الآلة أعلى ناتج (ويرمز له بـ Σ(n) )، أو تعمل لأطول وقت (S(n))، مقارنةً بباقي الآلات المنافسة ذات n حالات.

تحديد وقت التشغيل أو الناتج للـ n-قندس مشغول هو دالة غير قابلة للحساب. في الواقع، فإن كلا الدالتين Σ(n) وS(n) تتجاوزان في النهاية أي دالة قابلة للحساب. وهذا له تأثيرات على نظرية الحوسبة، ومسألة التوقف، ونظرية التعقيد الحسابي. PDF متاح  تم تقديم مفهوم القندس المشغول لأول مرة بواسطة تيبور رادو في ورقته البحثية عام 1962 بعنوان "حول الدوال غير القابلة للحساب". ومن أكثر الجوانب إثارة في لعبة القندس المشغول أنه، لو كان بالإمكان حساب الدالتين Σ(n) وS(n) لكل n، لكان بالإمكان حينها حسم جميع التخمينات الرياضية التي يمكن ترميزها على شكل "هل تتوقف <هذه آلة تورنغ>". على سبيل المثال، يمكن لآلة تورنغ ذات 27 حالة أن تتحقق من حدسية غولدباخ لكل عدد وتتوقف عند العثور على مثال مضاد: وإذا لم تتوقف هذه الآلة بعد تنفيذها S(27) خطوة، فإنها لا بد أن تعمل إلى الأبد، مما يحسم التخمين. ويمكن أيضًا التعبير عن العديد من المسائل الأخرى، بما في ذلك فرضية ريمان (744 حالة) واتساق نظرية المجموعات حسب تسيرميلو-فرانكل (745 حالة)، بطريقة مشابهة، حيث يمكن التحقق من عدد قابل للعد من الحالات على الأكثر.

 التعريف الفني 
لعبة القندس المشغول-إن (أو لعبة بي بي-إن)، التي قُدّمت في ورقة تيبور رادو عام 1962، تتعلق بفئة من آلة تورنغ، حيث يُطلب من كل عضو فيها أن يفي بالمواصفات التصميمية التالية:

 تحتوي الآلة على n حالة "تشغيلية" بالإضافة إلى حالة توقف، حيث إن n عدد صحيح موجب، وتُعتبر إحدى حالات n هي الحالة الابتدائية. (عادةً ما تُرقّم الحالات 1، 2، ...، n، مع كون الحالة 1 هي الابتدائية، أو بالحروف A، B، C، ...، مع كون الحالة A هي الابتدائية.)
 تستخدم الآلة شريطًا لا نهائيًا (أو غير محدود) في كلا الاتجاهين.
 أبجدية الشريط هي {0، 1}، حيث تُستخدم 0 كرمز فراغ.
 تأخذ دالة الانتقال للآلة مدخلين:
 الحالة الحالية غير حالة التوقف،
 الرمز في خلية الشريط الحالية،
وتُنتج ثلاث مخرجات:
 رمز لكتابته فوق الرمز في خلية الشريط الحالية (قد يكون هو نفسه الرمز الذي تتم الكتابة فوقه)،
 اتجاه للحركة (يسار أو يمين؛ أي الانتقال إلى خلية الشريط المجاورة إما لليسار أو اليمين من الخلية الحالية)،
 حالة للانتقال إليها (قد تكون حالة التوقف).

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

 مثال 
قد تكون قواعد آلة تورنغ ذات حالة واحدة كالتالي:
 في الحالة 1، إذا كان الرمز الحالي 0، اكتب 1، وتحرك خانة واحدة إلى اليمين، وانتقل إلى الحالة 1
 في الحالة 1، إذا كان الرمز الحالي 1، اكتب 0، وتحرك خانة واحدة إلى اليمين، وانتقل إلى التوقف (HALT)

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

 الدوال 
في ورقته الأصلية عام 1962، عرّف رادو دالتين تتعلقان بلعبة البيفر المشغول: دالة النتيجة Σ(n) ودالة الحركات S(n). كلتاهما تأخذ عددًا معينًا من حالات آلة تورنغ  وتُنتجان أعلى نتيجة ممكنة لآلة تورنغ بذلك العدد من الحالات حسب مقياس معين. تُعطي دالة النتيجة Σ(n) أكبر عدد من الآحاد يمكن أن تُنتجه آلة تورنغ ذات n حالة قبل التوقف، بينما تُعطي دالة الحركات S(n) أكبر عدد من الحركات (أو الخطوات، لأن كل خطوة تتضمن حركة) يمكن أن تقوم بها آلة تورنغ قبل التوقف. وقد أثبت أن كلتا الدالتين هما دالة غير قابلة للحساب، لأن كلًا منهما تنمو أسرع من أي دالة قابلة للحساب. تم تعريف الدالة بي بي-إن لتكون أيًا من هاتين الدالتين، لذا لا يُستخدم هذا الترميز في هذه المقالة.

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

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

 دالة النتيجة Σ 

تقيس دالة النتيجة الحد الأقصى للنتيجة التي يمكن أن يحققها "القندس المشغول" وفقًا لمقياس معين. وتُعد هذه دالة حسوبة، لأنها تنمو وفق تحليل مقارب أسرع من أي دالة قابلة للحوسبة.Chaitin (1987)

تُعرَّف دالة النتيجة  بحيث تكون Σ(n) هي الحد الأقصى الممكن للنتيجة (أي أكبر عدد من الرموز 1 المتبقية على الشريط في النهاية) بين جميع آلات تورنغ المتوقفة المكونة من n حالة ورمزين كما تم وصفها أعلاه، عند بدء تشغيلها على شريط فارغ.

ومن الواضح أن Σ دالة معرفة جيدًا: لكل n يوجد عدد منتهي (بحد أقصى) من آلات تورنغ ذات n حالة كما سبق، حتى حد التماثل البنيوي، وبالتالي فإن عدد أوقات التشغيل المحتملة أيضًا منتهٍ.

وفقًا لتعريف النتيجة، فإن أي آلة تورنغ مكونة من n حالة ورمزين تُسمى "قندسًا مشغولًا" إذا كانت  (أي إذا بلغت النتيجة القصوى). ولكل قيمة n، يوجد على الأقل 4(n − 1)! من "القنادس المشغولة" ذات n حالة. (فعند وجود آلة من هذا النوع، يمكن الحصول على أخرى بمجرد تغيير اتجاه الانتقال في خطوة الإيقاف، وثالثة بعكس **كل** اتجاهات الانتقال بشكل موحد، ورابعة بعكس اتجاه الإيقاف في "القندس" المعدل بالكامل. علاوة على ذلك، فإن تبديل ترتيب كل الحالات ما عدا الابتداء والتوقف يُنتج آلة تُحقق نفس النتيجة. من الناحية النظرية، يمكن أن توجد أكثر من عملية انتقال واحدة تؤدي إلى حالة التوقف، لكن في الممارسة سيكون ذلك غير فعّال، لأنه لا توجد سوى سلسلة واحدة من الانتقالات تؤدي إلى النتيجة المطلوبة.)

 عدم القابلية للحوسبة 

أثبت رادو في ورقته عام 1962 أن  إذا كانت أي دالة حسوبة، فإن Σ(n) > f(n) لكل قيم n الكبيرة بما فيه الكفاية، ومن ثم فإن Σ دالة غير قابلة للحوسبة.

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

على الرغم من أن Σ(n) دالة غير قابلة للحوسبة، إلا أنه من الممكن حساب قيمها وإثبات صحتها لبعض القيم الصغيرة لـn. ومن السهل إظهار أن Σ(0) = 0، Σ(1) = 1، Σ(2) = 4، وبمزيد من الجهد يمكن إثبات أن Σ(3) = 6، Σ(4) = 13، وΣ(5) = 4098 . ولم يتم حتى الآن تحديد Σ(n) لأي قيمة n > 5، رغم أنه قد تم إثبات بعض الحدود الدنيا لها (انظر قسم القيم المعروفة أدناه).

 التعقيد وعدم قابلية الإثبات لدالة Σ 

يُعرَّف نوع مختلف من تعقيد كولموغروف كما يلي:Boolos, Burgess & Jeffrey, 2007. "Computability and Logic" يُعرّف "تعقيد" عدد n بأنه أقل عدد من الحالات اللازمة لآلة تورنغ من فئة القندس المشغول تتوقف بعد أن تكتب كتلة واحدة من n رموز متتالية من الرقم 1 على شريط فارغ. ووفقًا للنوع المكافئ من تعقيد كولموغروف، فإنه في سياق نظام بديهيات معين للأعداد الطبيعية، يوجد عدد k لا يمكن إثبات أن أي عدد معين يمتلك تعقيدًا أكبر منه، وبالتالي لا يمكن إثبات أي حد أعلى محدد لـΣ(k) (لأن إثبات أن "تعقيد n أكبر من k" يستلزم إثبات أن ). وكما ورد في المرجع المشار إليه، فإن أقل قيمة لـk ينطبق عليها هذا الكلام في أي نظام بديهي لـ"الرياضيات العادية" هي أقل بكثير من 10⇈10؛ ونتيجة لذلك، لا يمكن في سياق الرياضيات العادية إثبات قيمة Σ(10⇈10) أو أي حد أعلى لها. (مبرهنات عدم الاكتمال لغودل تتضح من خلال هذه النتيجة: ففي نظام بديهي للرياضيات العادية، توجد جملة صحيحة ولكن غير قابلة للإثبات من الشكل ، كما توجد عدد لا نهائي من الجمل الصحيحة ولكن غير القابلة للإثبات من الشكل .)

 دالة أقصى عدد من التحركات S 
بالإضافة إلى الدالة Σ، قدّم رادو [1962] دالة قصوى أخرى للآلات التورينغ تُعرف باسم دالة أقصى عدد من التحركات، S، والتي تُعرّف كما يلي:

  = عدد التحركات التي يُجريها M قبل التوقف، لأي ،
  = أكبر عدد من التحركات التي تُجريها أي آلة تورينغ تتوقف من نوع "n حالة و2 رمزًا".

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

وقد بيّن رادو أن S غير قابلة للحساب لنفس السبب الذي يجعل Σ غير قابلة للحساب — فهي تنمو أسرع من أي دالة قابلة للحساب. وقد أثبت ذلك ببساطة من خلال ملاحظة أنه لكل n، فإن S(n) ≥ Σ(n). إذ إن كل تحرك قد يكتب 0 أو 1 على الشريط، في حين أن Σ تعد مجموعة فرعية من التحركات التي كتبت 1، وتحديدًا تلك التي لم تُكتب فوقها بحلول وقت توقف الآلة؛ وبالتالي، فإن S تنمو على الأقل بالسرعة نفسها التي تنمو بها Σ، والتي سبق أن ثبت أنها تنمو أسرع من أي دالة قابلة للحساب.

وقد استُخدمت العلاقة التالية بين Σ وS من قبل لين ورادو في بحثهم دراسات حاسوبية لمسائل آلة تورينج (1965) لإثبات أن Σ(3) = 6 وأن S(3)=21: بالنسبة لقيمة معينة لـ n، إذا كانت قيمة S(n) معروفة، يمكن نظريًا تشغيل جميع آلات تورينغ ذات n حالة حتى تصل إلى S(n) خطوة، وعندها فإن أي آلة لم تتوقف بعد تلك الخطوات لن تتوقف أبدًا. عند تلك النقطة، يمكن ملاحظة الآلات التي توقفت وفي شريطها أكبر عدد من الآحاد (أي "القنادس المنشغلة")، ومن خلال أشرطتها يمكن الحصول على قيمة Σ(n). الطريقة التي استخدمها لين ورادو في حالة n = 3 كانت عبر افتراض أن S(3) = 21 (بعد أن افترضوا سابقًا 18 دون نجاح)، ثم قاموا بمحاكاة جميع الآلات المختلفة جوهريًا ذات 3 حالات (وعددها 82,944 آلة، أي ما يعادل 23) حتى 21 خطوة. وقد وجدوا أن 26,073 آلة توقفت، من بينها آلة توقفت بعد 21 خطوة فقط. ومن خلال تحليل سلوك الآلات التي لم تتوقف خلال 21 خطوة، نجحوا في إثبات أن أياً منها لن يتوقف أبدًا، حيث اتبعت معظمها نمطًا معينًا. وقد أثبت هذا صحة الفرضية أن S(3) = 21، كما حدد أن Σ(3) = 6، والتي حققتها عدة آلات توقفت بعد ما بين 11 إلى 14 خطوة.

في عام 2016، حصل آدم يديديا وسكوت آرنسون على أول حد علوي (صريح) لأصغر قيمة لـ n بحيث تكون قيمة S(n) غير قابلة للإثبات ضمن نظرية المجموعات حسب تسيرميلو-فرانكل. للقيام بذلك، أنشأوا آلة تورينغ مكونة من 7910 حالة لا يمكن إثبات سلوكها بناءً على بديهيات نظرية المجموعات الشائعة (نظرية المجموعات حسب تسيرميلو-فرانكل مع بديهية الاختيار), بافتراض فرضيات اتساق معقولة (خاصية رامزي الثابتة).الإصدار المؤرخ 3 مايو احتوى على 7918 حالة:  لاحقًا خفّض ستيفان أورير عدد الحالات إلى 1919، مع إزالة الاعتماد على خاصية رامزي الثابتة، ثم إلى 748 حالة. وفي يوليو 2023، خفّض رايبل العدد إلى 745 حالة.

 برهان على عدم قابلية S(n) وΣ(n) للحساب 
افترض أن S(n) دالة قابلة للحساب، ولنرمز إلى آلة تورينغ التي تحسبها بـ إيفالس. عند إعطائها شريطًا يحتوي على n من الآحاد، ستنتج S(n) من الآحاد على الشريط ثم تتوقف. ولنُعرّف آلة كلين بأنها آلة تورينغ تنظف سلسلة الآحاد المكتوبة في البداية. ولنُعرّف آلة دوبل بأنها آلة تورينغ تحسب الدالة n + n، أي أنها تنتج 2n من الآحاد ثم تتوقف. لنُنشئ الآن التركيب التالي: دوبل | إيفالس | كلين، ولنفرض أن عدد حالات هذه الآلة هو n0. ولندع Create_n0 آلة تورينغ تُنشئ n0 من الآحاد على شريط فارغ، ويمكن بناء هذه الآلة بشكل بسيط بحيث تحتوي على n0 حالة (تقوم الحالة i بكتابة 1، ثم تحرك الرأس يمينًا وتنتقل إلى الحالة i + 1، ما عدا الحالة الأخيرة التي تتوقف). ولنُعرّف N بأنه المجموع: n0 + n0.

دع BadS هو تركيب الآلات: Create_n0 | دوبل | إيفالس | كلين. لاحظ أن هذه الآلة تحتوي على N حالة. تبدأ بشريط فارغ، فتُنشئ أولًا سلسلة من n0 من الآحاد، ثم تُضاعفها إلى سلسلة من N من الآحاد. بعد ذلك تُنتج S(N) من الآحاد، وأخيرًا تمسح الشريط وتتوقف. لكن مرحلة المسح تستغرق على الأقل S(N) خطوة، مما يعني أن زمن عمل BadS يفوق S(N)، وهو ما يتعارض مع تعريف الدالة S(n).

ويمكن إثبات عدم قابلية Σ(n) للحساب بطريقة مماثلة. في البرهان أعلاه، يُستبدل إيفالس بـ إيفالΣ، وكلين بـ إنكريمينت — وهي آلة تورينغ بسيطة تبحث عن أول 0 على الشريط وتستبدله بـ 1.

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

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

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

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

 أعداد مختلفة من الرموز 
أحد التعميمات البسيطة هو التوسيع ليشمل آلات تورنغ التي تحتوي على m من الرموز بدلاً من مجرد رمزَين (0 و1).
فعلى سبيل المثال، آلة تورنغ ثلاثية الرموز m = 3 ستكون لديها الرموز 0، 1، و2.
ويعرّف التعميم لآلات تورنغ التي تحتوي على n من الحالات وm من الرموز الدوال العامة التالية للقندس المشغول:
 Σ(n, m): أكبر عدد من الآحاد (أو القيم غير الصفرية) يمكن طباعته بواسطة آلة ذات n حالة وm رمزًا على شريط كان في البداية فارغًا، قبل أن تتوقف،
 S(n, m): أكبر عدد من الخطوات التي يمكن أن تقوم بها آلة ذات n حالة وm رمزًا على شريط كان في البداية فارغًا، قبل أن تتوقف.

على سبيل المثال، أطول آلة ذات 3 حالات و3 رموز تم اكتشافها حتى الآن تقوم بـ خطوة قبل أن تتوقف.

 الآلات تورنغ غير الحتمية 
+ أقصى أزمنة التوقف وعدد الحالات لآلات تورنغ غير الحتمية ذات حالتين ولونين وp حالة p عدد الخطوات عدد الحالات 1 2  2 2 4  4 3 6  7 4 7  11 5 8  15 6 7  18 7 6  18

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

 التطبيقات 

 مسائل رياضية مفتوحة 
إضافةً إلى كونها لعبة رياضية صعبة، توفر دوال القندس المشغول Σ(n) وS(n) مدخلًا جديدًا تمامًا لحل مسائل الرياضيات البحتة. فمن الناحية النظرية، يمكن حل العديد من قائمة المسائل غير المحلولة في الرياضيات بشكل منهجي إذا ما توفرت قيمة S(n) لعدد كافٍ من الحالات. فمبدئيًا، تحتوي قيمة S(n) على إجابات جميع الحدسيات الرياضية التي يمكن التحقق منها في وقت غير محدود باستخدام آلة تورنغ لا تتجاوز n حالة.

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

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

لكن، تشير النتائج الحالية المتعلقة بمسألة القندس المشغول إلى أن ذلك غير عملي لسببين:
 من الصعب جدًا إثبات قيم دالة القندس المشغول (ودالة الإزاحة القصوى). فقد تم إثبات كل قيمة معروفة لـ S(n) عن طريق تعداد جميع آلات تورنغ ذات n حالة وإثبات ما إذا كانت تتوقف أم لا. لا بد من إيجاد طريقة غير مباشرة لحساب S(n) كي تصبح مفيدة حقًا.
 قيم S(n) ودوال القندس المشغول الأخرى تزداد بشكل هائل وسريع جدًا. فعلى سبيل المثال، قيمة S(5) تبلغ حوالي 47 مليون فقط، بينما قيمة S(6) تتجاوز 10⇈15، أي  مع 15 عدد 10 متراكبًا. هذا الرقم يحتوي على 10⇈14 رقمًا وهو رقم غير عملي تمامًا للاستخدام في الحسابات. أما قيمة S(27)، وهي عدد الخطوات الذي يتعين على البرنامج الحالي لاختبار حدسية غولدباخ تشغيله لتقديم إجابة قاطعة، فهي هائلة بشكل يفوق الفهم، وغير قابلة للتسجيل أو التنفيذ حتى داخل الكون المرئي.

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

 أمثلة بارزة 
 تم بناء آلة تورنغ ثنائية بعدد 745 حالة تتوقف إذا وفقط إذا كانت نظرية المجموعات حسب تسيرميلو-فرانكل غير متسقة.
 تم بناء آلة تورنغ بعدد 744 حالة تتوقف إذا وفقط إذا كانت فرضية ريمان خاطئة.
 تم بناء آلة تورنغ بعدد 43 حالة تتوقف إذا وفقط إذا كانت حدسية غولدباخ خاطئة. ثم جرى تقليل ذلك إلى آلة ذات 25 حالة، ولاحقًا تم إثباتها والتحقق منها رسميًا باستخدام لغة إثبات النظريات لين 4.
 تم بناء آلة تورنغ بعدد 15 حالة تتوقف إذا وفقط إذا كانت التخمينية التالية التي صاغها بول إيردوش سنة 1979 خاطئة: لكل عدد n > 8، يوجد على الأقل رقم 2 واحد في تمثيل العدد 2n في الأساس الثلاثي.

 آلات تورنغ الشاملة 
أثناء استكشاف العلاقة بين الشمولية الحاسوبية والسلوك الديناميكي لآلات تورنغ من نوع "القندس المشغول"، تم اقتراح تخمين في عام 2012 PDF available from publisher. يفترض أن آلات "القندس المشغول" هي مرشح طبيعي للشمولية التورنجية لأنها تُظهر خصائص معقدة، تُعرف بـ (1) تعقيدها الحسابي الأقصى ضمن قيود الحجم، (2) قدرتها على إجراء حسابات غير تافهة قبل التوقف، و(3) صعوبة العثور عليها وإثبات خصائصها؛ وهذه الخصائص تشير إلى أن هذه الآلات تمتلك التعقيد اللازم لتحقيق الشمولية.

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

 النتائج المعروفة 
 الحدود الدنيا 

 آلات غرين 
في عام 1964، وضع ميلتون غرين حدًا أدنى لمتغير عدّ الـ1 في دالة القندس المشغول، ونُشر ذلك في وقائع ندوة IEEE لعام 1964 حول نظرية دوائر التحويل والتصميم المنطقي. وصف هاينر ماركسن ويورغن بونتروك هذا الحد بأنه «غير تافه (أي ليس أوليًا حسابيًا)». نسخة HTML مجانية من المؤلف  يمكن حساب هذا الحد الأدنى، لكنه معقد جدًا بحيث لا يمكن التعبير عنه بصيغة واحدة بدلالة n. تم هذا باستخدام مجموعة من آلات تورنغ، كل منها أظهر الحد الأدنى لقيمة معينة من n. عندما تكون n = 8 فإن الطريقة تعطي:
 .

وعلى النقيض، فإن أفضل حد أدنى معروف حاليًا (حتى عام 2024) لـ  هو ، حيث تشير كل  إلى ترميز السهم لأب كنوث. ويمثل هذا ، سلسلة أُسية مكوّنة من 15 عشرة متتالية، تساوي . ومن المحتمل أن تكون قيمة  أكبر بكثير من ذلك.

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




يؤدي هذا إلى صيغتين، للأعداد الفردية والزوجية، لحساب الحد الأدنى المعطى بواسطة الآلة رقم N، :
  للأعداد الفردية N
  للأعداد الزوجية N

يمكن أيضًا ربط الحد الأدنى BB(N) بـ دالة أكرمان. ويمكن إثبات أن:


 العلاقات بين دوال البيزي بيفر 

بديهياً، S(n) ≥ Σ(n) لأن الآلة التي تكتب Σ(n) واحدات يجب أن تأخذ على الأقل Σ(n) خطوة للقيام بذلك. من الممكن إعطاء عدة حدود عليا على الزمن S(n) بناءً على عدد الواحدات Σ(n):
  (رادو)
  (بورو)
  (بن-أمرام، جولستروم وزويك)

بتعريف num(n) على أنه الحد الأقصى لعدد الواحدات التي يسمح لآلة تورينج ذات n حالة بطباعتها متتالية، بدلاً من في أي موضع (أي أكبر نظام عد أحادي يمكنها طباعته)، يمكن إثبات:


  (بن-أمرام وآخرون، 1996)

بن-أمرام وبيترسن، 2002، قدموا أيضاً حدًا محسنًا أسيمبتوتيًا لـ S(n). هناك ثابت c، بحيث لكل :

 القيم الدقيقة والحدود الدنيا والعليا 

يعرض الجدول التالي القيم الدقيقة وبعض الحدود الدنيا المعروفة لـ S(n), Σ(n), وعدة دوال أخرى للبيزي بيفر. في هذا الجدول، تُستخدم آلات تورينج ذات رمزَين. الإدخالات المعلمة بعلامة "?" هي على الأقل بنفس حجم الإدخالات الموجودة على يسارها (لأن جميع الآلات ذات n حالة هي أيضاً آلات ذات (n+1) حالة)، وليست أكبر من الإدخالات التي فوقها (لأن S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)). لذا، من المعروف أن space(6) أكبر من 10⇈15، لأن space(n) ≥ Σ(n) وΣ(6) > 10⇈15. القيمة  هي حد علوي لـ space(5)، لأن S(5) =  () وS(n) ≥ space(n). العدد 4098 هو حد علوي لـ num(5)، لأن Σ(5) = 4098 () وΣ(n) ≥ num(n). الإدخال الأخير المعلم بـ "?" هو num(6)، لأن Σ(6) > 10⇈15، وΣ(n) ≥ num(n).

+ قيم دوال البيزي بيفر الدالة 2-حالة 3-حالة 4-حالة 5-حالة 6-حالة S(n)   6                 21                107                   > 10⇈15           space(n) 4   7   16   ≥  ≤ S(n) ≥ space(n)   > 10⇈15space(n) ≥ Σ(n)  Σ(n) 4   6   13   4098  > 10⇈15   num(n)4 6 12 ≤ 4098Σ(n) ≥ num(n) ? 

تم اكتشاف البيزي بيفر ذي الـ 5 حالات بواسطة هاينر ماركسن ويورغن بونتروك في 1989، ولكن لم يُثبت كونه الفائز بالمرتبة الخامسة — ويرمز له بـ BB(5) — إلا في 2024 باستخدام برهان في كووك.

 قائمة النماذج المشغولة 
مُصغّر|480px|رسم بياني مكبر للزمن-المكان لنموذج النشيط ذو 5 حالات (للتابع S(n)، ثم Σ(n)). يعمل النموذج لمدة 47,176,870 خطوة، ويبلغ ذروته بـ 12288 رقم واحد، ويترك 4098 رقم واحد عند التوقف.الرسوم مضغوطة بحيث تظهر فقط الخطوات التي تغير الشريط. تشير المثلثات الخضراء والصفراء إلى مناطق يتحرك فيها النموذج ذهابًا وإيابًا؛ والوقت المستغرق يتناسب مع مساحة هذه المثلثات الملونة. الصف الأسفل هو مقتطف من الشريط ورأس القراءة/الكتابة عند التوقف.

هذه جداول قواعد لآلات تورينج التي تولد Σ(1) وS(1)، Σ(2) وS(2)، Σ(3) (لكن ليس S(3))، Σ(4) وS(4)، Σ(5) وS(5)، وأفضل حد أدنى معروف لـ Σ(6) وS(6).

في الجداول، تمثل الأعمدة الحالة الحالية وتمثل الصفوف الرمز الحالي المقروء من الشريط. كل خانة في الجدول هي سلسلة من ثلاثة أحرف، تشير إلى الرمز الذي يُكتب على الشريط، والاتجاه الذي يتحرك إليه الرأس، والحالة الجديدة (بالترتيب). حالة التوقف تُعرض كـ H.

تبدأ كل آلة في الحالة A مع شريط لا نهائي يحتوي على أصفار فقط. لذا، الرمز الأول المقروء هو 0.

مفتاح النتيجة: (تبدأ عند الموقع ، وتتوقف عند الموقع )

{| class="wikitable"
|+ النشيط ذو الحالة الواحدة والرمزين
! width="20px" |
! A
|-
! 0
| 1RH
|-
! 1
| (غير مستخدم)
|}

النتيجة: 0 0   0 (خطوة واحدة، واحد "1" إجمالًا)

{| class="wikitable"
|+ النشيط ذو الحالتين والرمزين
! width="20px" |
! A
! B
|-
! 0
| 1RB
| 1LA
|-
! 1
| 1LB
| 1RH
|}

النتيجة: 0 0 1 1  1 0 0 (6 خطوات، أربعة "1" إجمالًا)

مُصغّر|تحريك لنموذج نشيط ذو 3 حالات ورمزين

{| class="wikitable"
|+ النشيط ذو 3 حالات ورمزين
! width="20px" |
! A
! B
! C
|-
! 0
| 1RB
| 0RC
| 1LC
|-
! 1
| 1RH
| 1RB
| 1LA
|}

النتيجة: 0 0 1  1  1 1 0 0 (14 خطوة، ستة "1" إجمالًا).

هذا واحد من عدة آلات غير مكافئة تعطي ستة 1s. بخلاف الآلات السابقة، هذه هي نشيطة للتابع Σ، لكنها ليست كذلك لـS. (S(3) = 21، وهذه الآلة تحصل فقط على خمسة 1s.)

مُصغّر|تحريك لنموذج نشيط ذو 4 حالات ورمزين

{| class="wikitable"
|+ النشيط ذو 4 حالات ورمزين
! width="20px" |
! A
! B
! C
! D
|-
! 0
| 1RB
| 1LA
| 1RH
| 1RD
|-
! 1
| 1LB
| 0LC
| 1LD
| 0RA
|}

النتيجة: 0 0 1  1 1 1 1 1 1 1 1  1 1 1 0 0 (107 خطوات، ثلاثة عشر "1" إجمالًا)

مُصغّر|300px|هذا "الرسم الزمني-المكاني" يظهر حالة شريط الذاكرة في صف لكل 100,000 خطوة من أفضل نشيط ذو 5 حالات من الأعلى إلى الأسفل. اللون البرتقالي هو "1"، والأبيض هو "0" (صورة مضغوطة عمودياً).

{| class="wikitable"
|+ النشيط ذو 5 حالات ورمزين
! width="20px" |
! A
! B
! C
! D
! E
|-
! 0
| 1RB
| 1RC
| 1RD
| 1LA
| 1RH
|-
! 1
| 1LC
| 1RB
| 0LE
| 1LD
| 0LA
|}

النتيجة: 4098 "1" مع 8191 "0" موزعة خلال 47,176,870 خطوة.

لاحظ في الصورة إلى اليمين كيف أن هذا الحل يشبه نوعيًا تطور بعض مصفوفة خلايا ذاتية التشغيل.

{| class="wikitable"
|+ أفضل منافس حالي ذو 6 حالات ورمزينصفحة مسابقات نموذج النشيط ل Pascal Michel  
! width="20px" |
! A
! B
! C
! D
! E
! F
|-
! 0
| 1RB
| 1RC
| 1LC
| 0LE
| 1LF
| 0RC
|-
! 1
| 0LD
| 0RF
| 1LA
| 1RH
| 0RB
| 0RE
|}

النتيجة: 1  1 1 1 ... 1 1 1 ("10" متبوعة بأكثر من 10↑↑15 رقم واحد متتالي في أكثر من 10↑↑15 خطوة، حيث 10↑↑15=1010..10، وهو برج أُسّي مكوّن من 15 عشرة).

 التصورات 

في الجدول التالي، تمثَّلت قواعد كل "بيزبيفر" (المُعظِّم لـ Σ) بصريًا، حيث تمثل المربعات البرتقالية الرقم "1" على الشريط، واللون الأبيض يمثل الرقم "0". يتم الإشارة إلى موقع الرأس بواسطة شكل بيضاوي أسود، مع تمثيل اتجاه الرأس للحالة الحالية. يتم عرض الشرائط بشكل أفقي، ويتقدم الزمن من الأعلى إلى الأسفل. تمثل حالة التوقف قاعدة تُطابق حالة واحدة مع نفسها (أي أن الرأس لا يتحرك).

 الملاحظات 

 المراجع 


 This is where Radó first defined the busy beaver problem and proved that it was uncomputable and grew faster than any computable function.

 The results of this paper had already appeared in part in Lin's 1963 doctoral dissertation, under Radó's guidance. Lin & Radó prove that Σ(3) = 6 and S(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt within 21 steps will never halt. (Most are proven automatically by a computer program, however 40 are proven by human inspection.)

 Brady proves that Σ(4) = 13 and S(4) = 107. Brady defines two new categories for non-halting 3-state 2-symbol Turing Machines: Christmas Trees and Counters. He uses a computer program to prove that all but 27 machines which run over 107 steps are variants of Christmas Trees and Counters which can be proven to run infinitely. The last 27 machines (referred to as holdouts) are proven by personal inspection by Brady himself not to halt.

 Machlin and Stout describe the busy beaver problem and many techniques used for finding busy beavers (which they apply to Turing Machines with 4-states and 2-symbols, thus verifying Brady's proof). They suggest how to estimate a variant of Chaitin's halting probability (Ω).

 Marxen and Buntrock demonstrate that Σ(5) ≥ 4098 and S(5) ≥  and describe in detail the method they used to find these machines and prove many others will never halt.

 Green recursively constructs machines for any number of states and provides the recursive function that computes their score (computes σ), thus providing a lower bound for Σ. This function's growth is comparable to that of دالة أكرمان.

 Busy beaver programs are described by Alexander Dewdney in Scientific American, August 1984, pages 19–23, also March 1985 p. 23 and April 1985 p. 30.


 Wherein Brady (of 4-state fame) describes some history of the beast and calls its pursuit "The Busy Beaver Game". He describes other games (e.g. مصفوفة خلايا ذاتية التشغيل and لعبة الحياة (حوسبة)). Of particular interest is "The Busy Beaver Game in Two Dimensions" (p. 247). With 19 references.

 Cf Chapter 9, Turing Machines. A difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. A reference in Booth attributes busy beaver to Rado. Booth also defines Rado's busy beaver problem in "home problems" 3, 4, 5, 6 of Chapter 9, p. 396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n."

 Improved bounds.

 This article contains a complete classification of the 2-state, 3-symbol Turing machines, and thus a proof for the (2, 3) busy beaver: Σ(2, 3) = 9 and S(2, 3) = 38.


 This is the description of ideas, of the algorithms and their implementation, with the description of the experiments examining 5-state and 6-state Turing machines by parallel run on 31 4-core computer and finally the best results for 6-state TM.

 روابط خارجية 

 صفحة هاينر ماركسن، الذي وجد مع يورغن بونتروك الأرقام القياسية المذكورة أعلاه لآلة تورينغ ذات 5 و6 حالات.
 مسح تاريخي لنتائج بيزِي بيفر من إعداد باسكال ميشيل، يحتوي أيضًا على أفضل النتائج وبعض التحليلات.
 تعريف الفئة RTM - آلات تورينغ العكسية، فئة فرعية بسيطة وقوية من آلات تورينغ.
 "مشكلة بيزِي بيفر: هجوم الألفية الجديدة" (مؤرشف) في مختبر رينسيلير RAIR. هذا الجهد أسفر عن إيجاد عدة أرقام قياسية جديدة وتثبيت عدة قيم للتصميم الرباعي.
 موقع دانييل بريغز مؤرشف ومنتدى لحل مشكلة بيزِي بيفر ذات 5 حالات ورمزين، بالاعتماد على قائمة الآلات غير النظامية Skelet (جيورجي جيورجيف).

 آرونسون، سكوت (1999)، من يمكنه تسمية الرقم الأكبر؟

 آلات تورينغ بيزِي بيفر - كمبيوترفايل، يوتيوب
 باسكال ميشيل. مسابقة بيزِي بيفر: مسح تاريخي. 70 صفحة. 2017. <hal-00396880v5>

تصنيف:نظرية الحسوبية
تصنيف:النظرية الحسابية
تصنيف:أعداد صحيحة كبيرة
تصنيف:مجازات تشير إلى حيوانات