hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
التوقيت الصيفي في أفريقيا الدول الأفريقية التي كانت تستخدم التوقيت الصيفي سابقًا
عند استقلال ناميبيا، ورثت البلاد تنظيمات التوقيت الخاصة بجنوب أفريقيا، وكانت ضمن المنطقة الزمنية UTC+02:00 على مدار السنة.من عام 1994 حتى عام 2017، استخدمت ناميبيا التوقيت الشتوي، وهو إجراء تقديم الساعة ساعة واحدة إلى الوراء خلال أشهر الشتاء. في هذه الفترة، كان التوقيت القياسي لناميبيا UTC+02:00 (توقيت وسط أفريقيا) في الصيف، وUTC+01:00 (توقيت غرب أفريقيا) في الشتاء.[بحاجة لمصدر] ُدخل هذا التغيير الذي أُطلق عليه اسم “التوقيت القياسي لناميبيا” في عام 1993، بسبب المخاوف من ذهاب الأطفال إلى المدارس قبل شروق الشمس. يبدأ التوقيت الشتوي في أول أحد من أبريل عند الساعة 03:00، ويستمر حتى أول أحد من سبتمبر عند الساعة 02:00.في منطقة زامبيزي الواقعة في أقصى شمال شرق ناميبيا، لم يتم تغيير الساعة وظلت على توقيت وسط أفريقيا طوال العام، مما أدى إلى انتشار ناميبيا على منطقتين زمنيتين خلال الشتاء.في العقد 2010، تكررت الدعوات من قبل الشركات والأفراد لإلغاء التوقيت الشتوي، مشيرين إلى عدم التوافق مع جنوب أفريقيا، الشريك التجاري الرئيسي لناميبيا، بالإضافة إلى “فقدان الإنتاجية”.وافق المجلس الوطني على مشروع قانون توقيت ناميبيا لعام 2017 في أغسطس 2017 وألغى قانون عام 1993،مما أعاد ناميبيا إلى المنطقة الزمنية القياسية لجنوب أفريقيا UTC+02:00.
تبنّت تونس التوقيت الصيفي لأول مرة في عام 2005، بدءًا من 1 مايو 2005، مع الالتزام بعد ذلك بجداول التوقيت الخاصة بالاتحاد الأوروبي. جاء ذلك كخطوة من الحكومة لتعزيز ترشيد استهلاك الطاقة. في عام 2009، ألغت الحكومة التوقيت الصيفي واحتفظت بالتوقيت القياسي على مدار السنة.
التوقيت الصيفي في أفريقيا الدول الأفريقية التي لا تستخدم التوقيت الصيفي
هذه البلدان أو المناطق لا تستخدم التوقيت الصيفي، على الرغم من أن بعضها كان يستخدمه في الماضي:
القندس المشغول
في علم الحاسوب النظري، تهدف لعبة القندس المشغول (بالإنجليزية: Busy beaver) إلى إيجاد برنامج يتوقف ويكون (وفقًا للتعريف) إما أنه ينتج أكبر كمية ممكنة من الخرج، أو يعمل لأطول عدد ممكن من الخطوات. وبما أن بإمكان برنامجٍ ما أن يعمل إلى ما لا نهاية أو ينتج خرجًا لانهائيًا، فإن هذه البرامج تُستبعد من اللعبة. بدلًا من لغات البرمجة التقليدية، تُستخدم في اللعبة آلات تورنغ ذات n حالات، وهي من أوائل النماذج الرياضية للحوسبة.
القندس المشغول
تتكون آلات تورنغ من شريط لا نهائي، ومجموعة من الحالات المنتهية التي تعمل كـ"كود مصدر" للبرنامج. يُعرّف إنتاج أكبر ناتج بكونه كتابة أكبر عدد من الرقم 1 على الشريط، ويُعرف التشغيل الأطول بأنه تنفيذ أكبر عدد من الخطوات قبل التوقف. تتكوّن لعبة القندس المشغول ذات n حالات من إيجاد آلة تورنغ تتوقف وتُنتج أكبر ناتج أو تعمل لأطول وقت ممكن بين جميع الآلات الممكنة ذات n حالات. تُفترض هذه الآلات بأنها تبدأ على شريطٍ فارغ، يحتوي فقط على الأصفار والآحاد (آلة تورنغ ثنائية). هدف اللعبة هو برمجة مجموعة من الانتقالات بين الحالات لتحقيق أعلى ناتج أو أطول وقت تشغيل مع ضمان توقّف الآلة في النهاية.
يُطلق على آلة تورنغ التي تفوز في لعبة القندس المشغول ذات n حالات اسم قندس مشغول-إن (بالإنجليزية: Busy beaver-n)، أو ببساطة "قندس مشغول"، وتُرمز إليها بـ بي بي-إن. وفقًا للتعريف، إما أن تُحقق هذه الآلة أعلى ناتج (ويرمز له بـ Σ(n) )، أو تعمل لأطول وقت (S(n))، مقارنةً بباقي الآلات المنافسة ذات n حالات.
القندس المشغول
تحديد وقت التشغيل أو الناتج للـ n-قندس مشغول هو دالة غير قابلة للحساب. في الواقع، فإن كلا الدالتين Σ(n) وS(n) تتجاوزان في النهاية أي دالة قابلة للحساب. وهذا له تأثيرات على نظرية الحوسبة، ومسألة التوقف، ونظرية التعقيد الحسابي. تم تقديم مفهوم القندس المشغول لأول مرة بواسطة تيبور رادو في ورقته البحثية عام 1962 بعنوان "حول الدوال غير القابلة للحساب". ومن أكثر الجوانب إثارة في لعبة القندس المشغول أنه، لو كان بالإمكان حساب الدالتين Σ(n) وS(n) لكل n، لكان بالإمكان حينها حسم جميع التخمينات الرياضية التي يمكن ترميزها على شكل "هل تتوقف <هذه آلة تورنغ>". على سبيل المثال، يمكن لآلة تورنغ ذات 27 حالة أن تتحقق من حدسية غولدباخ لكل عدد وتتوقف عند العثور على مثال مضاد: وإذا لم تتوقف هذه الآلة بعد تنفيذها S(27) خطوة، فإنها لا بد أن تعمل إلى الأبد، مما يحسم التخمين. ويمكن أيضًا التعبير عن العديد من المسائل الأخرى، بما في ذلك فرضية ريمان (744 حالة) واتساق نظرية المجموعات حسب تسيرميلو-فرانكل (745 حالة)، بطريقة مشابهة، حيث يمكن التحقق من عدد قابل للعد من الحالات على الأكثر.
القندس المشغول التعريف الفني
لعبة القندس المشغول-إن (أو لعبة بي بي-إن)، التي قُدّمت في ورقة تيبور رادو عام 1962، تتعلق بفئة من آلة تورنغ، حيث يُطلب من كل عضو فيها أن يفي بالمواصفات التصميمية التالية:
تحتوي الآلة على n حالة "تشغيلية" بالإضافة إلى حالة توقف، حيث إن n عدد صحيح موجب، وتُعتبر إحدى حالات n هي الحالة الابتدائية. (عادةً ما تُرقّم الحالات 1، 2، ...، n، مع كون الحالة 1 هي الابتدائية، أو بالحروف A، B، C، ...، مع كون الحالة A هي الابتدائية.)
الحالة الحالية غير حالة التوقف،
الرمز في خلية الشريط الحالية،
وتُنتج ثلاث مخرجات:
رمز لكتابته فوق الرمز في خلية الشريط الحالية (قد يكون هو نفسه الرمز الذي تتم الكتابة فوقه)،
اتجاه للحركة (يسار أو يمين؛ أي الانتقال إلى خلية الشريط المجاورة إما لليسار أو اليمين من الخلية الحالية)،
حالة للانتقال إليها (قد تكون حالة التوقف).
القندس المشغول التعريف الفني
يتضمن "تشغيل" الآلة البدء من الحالة الابتدائية، مع اعتبار خلية الشريط الحالية هي أي خلية من شريط فارغ (كله أصفار)، ثم تكرار دالة الانتقال حتى الوصول إلى حالة التوقف (إن حدث ذلك). إذا، وفقط إذا، توقفت الآلة في النهاية، فإن عدد الآحاد المتبقية على الشريط يُسمى "نتيجة" الآلة. وبالتالي فإن لعبة البيفر المشغول ذات n حالات (BB-n) هي منافسة تهدف، حسب التعريف، إلى إيجاد آلة تورنغ بعدد n من الحالات تُنتج أعلى نتيجة ممكنة أو أطول وقت تشغيل.
قد تكون قواعد آلة تورنغ ذات حالة واحدة كالتالي:
تقوم هذه الآلة بالتحرك إلى اليمين وتبديل قيمة جميع الخلايا التي تمر بها. وبما أن الشريط الابتدائي كله أصفار، فإنها ستُنتج سلسلة لا نهائية من الآحاد. هذه الآلة لا تُعتبر مرشحة للبيفر المشغول لأنها تعمل إلى ما لا نهاية على شريط فارغ.
القندس المشغول الدوال
في ورقته الأصلية عام 1962، عرّف رادو دالتين تتعلقان بلعبة البيفر المشغول: دالة النتيجة Σ(n) ودالة الحركات S(n). كلتاهما تأخذ عددًا معينًا من حالات آلة تورنغ  وتُنتجان أعلى نتيجة ممكنة لآلة تورنغ بذلك العدد من الحالات حسب مقياس معين. تُعطي دالة النتيجة Σ(n) أكبر عدد من الآحاد يمكن أن تُنتجه آلة تورنغ ذات n حالة قبل التوقف، بينما تُعطي دالة الحركات S(n) أكبر عدد من الحركات (أو الخطوات، لأن كل خطوة تتضمن حركة) يمكن أن تقوم بها آلة تورنغ قبل التوقف. وقد أثبت أن كلتا الدالتين هما دالة غير قابلة للحساب، لأن كلًا منهما تنمو أسرع من أي دالة قابلة للحساب. تم تعريف الدالة بي بي-إن لتكون أيًا من هاتين الدالتين،[بحاجة لمصدر] لذا لا يُستخدم هذا الترميز في هذه المقالة.
يمكن أيضًا تعريف عدد من الدوال غير القابلة للحساب بناءً على قياس أداء آلات تورنغ بطرق أخرى غير الوقت أو عدد الآحاد الأقصى. على سبيل المثال:
تُعرّف الدالة  بأنها أقصى عدد من الآحاد المتجاورة يمكن أن تكتبها آلة تورنغ تتوقف على شريط فارغ. بعبارة أخرى، هذا هو أكبر نظام عد أحادي يمكن أن تكتبه آلة تورنغ ذات n حالة على الشريط.
القندس المشغول الدوال
تُعرّف الدالة  بأنها أكبر عدد من خلايا الشريط يمكن لآلة تورنغ تتوقف أن تقرأها (أي تزورها) قبل التوقف. يشمل ذلك الخلية الابتدائية، لكن لا يشمل الخلية التي تصل إليها الآلة فقط بعد انتقال التوقف (إذا كان انتقال التوقف مُحددًا باتجاه حركة)، لأن هذه الخلية لا تؤثر في سلوك الآلة. تمثل هذه الدالة الحد الأقصى لتعقيد المساحة لآلة تورنغ ذات n حالة.
ترتبط هذه الدوال الأربع بالعلاقة . يمكن أيضًا تعريف المزيد من الدوال من خلال تشغيل اللعبة على آلات حسابية مختلفة، مثل آلات تورنغ ذات ثلاثة رموز، أو آلات تورنغ غير حتمية، أو التكامل لامدا (متسلسلة A333479 في OEIS) أو حتى لغات برمجة عشوائية.
تقيس دالة النتيجة الحد الأقصى للنتيجة التي يمكن أن يحققها "القندس المشغول" وفقًا لمقياس معين. وتُعد هذه دالة حسوبة، لأنها تنمو وفق تحليل مقارب أسرع من أي دالة قابلة للحوسبة.
تُعرَّف دالة النتيجة  بحيث تكون Σ(n) هي الحد الأقصى الممكن للنتيجة (أي أكبر عدد من الرموز 1 المتبقية على الشريط في النهاية) بين جميع آلات تورنغ المتوقفة المكونة من n حالة ورمزين كما تم وصفها أعلاه، عند بدء تشغيلها على شريط فارغ.
القندس المشغول الدوال
ومن الواضح أن Σ دالة معرفة جيدًا: لكل n يوجد عدد منتهي (بحد أقصى) من آلات تورنغ ذات n حالة كما سبق، حتى حد التماثل البنيوي، وبالتالي فإن عدد أوقات التشغيل المحتملة أيضًا منتهٍ.
وفقًا لتعريف النتيجة، فإن أي آلة تورنغ مكونة من n حالة ورمزين تُسمى "قندسًا مشغولًا" إذا كانت σ(M) = Σ(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 (متسلسلة A028444 في OEIS). ولم يتم حتى الآن تحديد Σ(n) لأي قيمة n > 5، رغم أنه قد تم إثبات بعض الحدود الدنيا لها (انظر قسم القيم المعروفة أدناه).
القندس المشغول الدوال
يُعرَّف نوع مختلف من تعقيد كولموغروف كما يلي: يُعرّف "تعقيد" عدد n بأنه أقل عدد من الحالات اللازمة لآلة تورنغ من فئة القندس المشغول تتوقف بعد أن تكتب كتلة واحدة من n رموز متتالية من الرقم 1 على شريط فارغ. ووفقًا للنوع المكافئ من تعقيد كولموغروف، فإنه في سياق نظام بديهيات معين للأعداد الطبيعية، يوجد عدد k لا يمكن إثبات أن أي عدد معين يمتلك تعقيدًا أكبر منه، وبالتالي لا يمكن إثبات أي حد أعلى محدد لـΣ(k) (لأن إثبات أن "تعقيد n أكبر من k" يستلزم إثبات أن n > Σ(k)). وكما ورد في المرجع المشار إليه، فإن أقل قيمة لـk ينطبق عليها هذا الكلام في أي نظام بديهي لـ"الرياضيات العادية" هي أقل بكثير من 10⇈10؛ ونتيجة لذلك، لا يمكن في سياق الرياضيات العادية إثبات قيمة Σ(10⇈10) أو أي حد أعلى لها. (مبرهنات عدم الاكتمال لغودل تتضح من خلال هذه النتيجة: ففي نظام بديهي للرياضيات العادية، توجد جملة صحيحة ولكن غير قابلة للإثبات من الشكل Σ(10⇈10) = n، كما توجد عدد لا نهائي من الجمل الصحيحة ولكن غير القابلة للإثبات من الشكل Σ(10⇈10) < n.)
القندس المشغول الدوال
بالإضافة إلى الدالة Σ، قدّم رادو [1962] دالة قصوى أخرى للآلات التورينغ تُعرف باسم دالة أقصى عدد من التحركات، S، والتي تُعرّف كما يلي:
نظرًا لأن آلات تورينغ العادية يُشترط أن تُجري تحركًا في كل انتقال أو "خطوة" (بما في ذلك الانتقال إلى الحالة النهائية 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 آلة، أي ما يعادل 21034) حتى 21 خطوة. وقد وجدوا أن 26,073 آلة توقفت، من بينها آلة توقفت بعد 21 خطوة فقط. ومن خلال تحليل سلوك الآلات التي لم تتوقف خلال 21 خطوة، نجحوا في إثبات أن أياً منها لن يتوقف أبدًا، حيث اتبعت معظمها نمطًا معينًا. وقد أثبت هذا صحة الفرضية أن S(3) = 21، كما حدد أن Σ(3) = 6، والتي حققتها عدة آلات توقفت بعد ما بين 11 إلى 14 خطوة.
القندس المشغول الدوال
في عام 2016، حصل آدم يديديا وسكوت آرنسون على أول حد علوي (صريح) لأصغر قيمة لـ n بحيث تكون قيمة S(n) غير قابلة للإثبات ضمن نظرية المجموعات حسب تسيرميلو-فرانكل. للقيام بذلك، أنشأوا آلة تورينغ مكونة من 7910 حالة لا يمكن إثبات سلوكها بناءً على بديهيات نظرية المجموعات الشائعة (نظرية المجموعات حسب تسيرميلو-فرانكل مع بديهية الاختيار), بافتراض فرضيات اتساق معقولة (خاصية رامزي الثابتة). لاحقًا خفّض ستيفان أورير عدد الحالات إلى 1919، مع إزالة الاعتماد على خاصية رامزي الثابتة، ثم إلى 748 حالة. وفي يوليو 2023، خفّض رايبل العدد إلى 745 حالة.
القندس المشغول الدوال
افترض أن 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) لا بد أن تكون كذلك.
كل من الدالتين  و غير قابلتين للحساب. يمكن إثبات عدم قابلية حساب  من خلال ملاحظة أن كل مربع على الشريط تكتب عليه آلة تورنغ الرقم واحد يجب أن تمر عليه أيضًا؛ وبعبارة أخرى، .
أما بالنسبة لدالة ، فيمكن إثبات عدم قابليتها للحساب، على سبيل المثال، من خلال إثبات أن ، ويتم ذلك عن طريق تصميم آلة تورنغ ذات "(3n+3)" حالة تقوم بمحاكاة آلة تورنغ ذات n حالة التي تمثل البطل في استهلاك المساحة، وتستخدمها لكتابة ما لا يقل عن  من الآحاد المتجاورة على الشريط.
القندس المشغول تعميمات
يمكن تعريف نظائر لدالة الإزاحة ببساطة في أي لغة برمجة، بشرط أن يتم تمثيل البرامج كسلاسل من البتات، وأن يكون بالإمكان حساب عدد خطوات البرنامج.
فعلى سبيل المثال، يمكن تعميم لعبة القندس المشغول إلى بعدين باستخدام آلات تورنغ تعمل على أشرطة ثنائية الأبعاد، أو آلات تورنغ يُسمح لها بالبقاء في نفس الموضع بالإضافة إلى التحرك يمينًا ويسارًا.
وبدلاً من ذلك، يمكن تعريف "دالة القندس المشغول" لنماذج حوسبة مختلفة باستخدام تعقيد كولموغروف.
ويتم ذلك بأخذ  ليكون أكبر عدد صحيح  بحيث ، حيث  هو طول أقصر برنامج في  يقوم بإنتاج : وبهذا، فإن  هو أكبر عدد صحيح يمكن لبرنامج بطول  أو أقل أن ينتجه في .
أطول آلة تورنغ معروفة حتى الآن ذات 6 حالات ورمزين وتملك الخاصية الإضافية التي تقلب قيمة الشريط في كل خطوة، تنتج 6147 من الآحاد بعد 47339970 خطوة.[بحاجة لمصدر]
وعليه، في فئة آلة تورنغ الانعكاسية (RTM)، فإن SRTM(6) ≥ 47339970 وΣRTM(6) ≥ 6147.
وبالمثل، يمكننا تعريف نظير لدالة Σ لآلات آلة السجل على أنه أكبر عدد يمكن أن يظهر في أي سجل عند التوقف، لعدد معين من التعليمات.[بحاجة لمصدر]
القندس المشغول تعميمات
أحد التعميمات البسيطة هو التوسيع ليشمل آلات تورنغ التي تحتوي على m من الرموز بدلاً من مجرد رمزَين (0 و1).
فعلى سبيل المثال، آلة تورنغ ثلاثية الرموز m = 3 ستكون لديها الرموز 0، 1، و2.
ويعرّف التعميم لآلات تورنغ التي تحتوي على n من الحالات وm من الرموز الدوال العامة التالية للقندس المشغول:
على سبيل المثال، أطول آلة ذات 3 حالات و3 رموز تم اكتشافها حتى الآن تقوم بـ119112334170342540 خطوة قبل أن تتوقف.
يمكن توسيع المسألة لتشمل آلة تورنغ غير الحتمية من خلال البحث عن النظام الذي يحقق أكبر عدد من الحالات عبر جميع الفروع أو الفرع الذي يستغرق أكبر عدد من الخطوات. تظل مسألة ما إذا كانت آلة تورنغ غير الحتمية ستتوقف غير قابلة للاختزال حسابيًا، كما أن مقدار الحساب اللازم لإيجاد "القندس المشغول" لهذه الفئة أكبر بكثير مقارنة بالحالة الحتمية، إذ يجب أخذ عدة فروع في الاعتبار. بالنسبة لنظام بحالتين ولونين و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) يمكنها إثباتها. ويعود السبب في ذلك إلى أنه يمكن تصميم آلة تورنغ بعدد  من الحالات لتقوم بتعداد جميع الإثباتات الممكنة في . وإذا كانت النظرية غير متسقة، فإن جميع العبارات الخاطئة تصبح قابلة للإثبات، ويمكن إعطاء آلة تورنغ شرط التوقف فقط إذا وجدت إثباتًا لعبارة مثل . أي نظرية تثبت قيمة  تكون قد أثبتت اتساقها الداخلي، مما ينتهك مبرهنات عدم الاكتمال لغودل. يمكن استخدام هذه الخاصية لترتيب النظريات على سلم، على سبيل المثال بديهيات الكرديناليات الكبيرة في نظرية المجموعات حسب تسيرميلو-فرانكل: إذا أُسند لكل نظرية  العدد ، فإن النظريات ذات القيم الأعلى لـ  تثبت اتساق النظريات ذات القيم الأدنى، مما يضع كل هذه النظريات على سلم قابل للعد لا نهائي.
القندس المشغول التطبيقات
تم بناء آلة تورنغ بعدد 43 حالة تتوقف إذا وفقط إذا كانت حدسية غولدباخ خاطئة. ثم جرى تقليل ذلك إلى آلة ذات 25 حالة، ولاحقًا تم إثباتها والتحقق منها رسميًا باستخدام لغة إثبات النظريات لين 4.
تم بناء آلة تورنغ بعدد 15 حالة تتوقف إذا وفقط إذا كانت التخمينية التالية التي صاغها بول إيردوش سنة 1979 خاطئة: لكل عدد n > 8، يوجد على الأقل رقم 2 واحد في تمثيل العدد 2n في الأساس الثلاثي.
أثناء استكشاف العلاقة بين الشمولية الحاسوبية والسلوك الديناميكي لآلات تورنغ من نوع "القندس المشغول"، تم اقتراح تخمين في عام 2012 يفترض أن آلات "القندس المشغول" هي مرشح طبيعي للشمولية التورنجية لأنها تُظهر خصائص معقدة، تُعرف بـ (1) تعقيدها الحسابي الأقصى ضمن قيود الحجم، (2) قدرتها على إجراء حسابات غير تافهة قبل التوقف، و(3) صعوبة العثور عليها وإثبات خصائصها؛ وهذه الخصائص تشير إلى أن هذه الآلات تمتلك التعقيد اللازم لتحقيق الشمولية.
تمتلك خصائص نمو دالة "القندس المشغول" تبعات على سلوك الأنظمة الفيزيائية، بافتراض صحة أطروحة تشرش-تورينغ. فإذا كانت هذه الأطروحة الفيزيائية صحيحة، وكل الدوال القابلة للحوسبة فيزيائيًا قابلة للحوسبة بواسطة آلة تورنغ، فإنه لا يمكن لأي كمية فيزيائية قابلة للقياس المباشر أن تنمو أسرع من دالة "القندس المشغول"، لأن أي دالة قابلة للحوسبة بواسطة آلة تورنغ لا يمكن أن تنمو أسرع منها. كما أن الدوال البسيطة المرتبطة بـ  تفرض أيضًا حدًا أدنى على معدلات النمو، بالإضافة إلى حدود عليا وسفلى على معدلات التقارب.
القندس المشغول النتائج المعروفة
في عام 1964، وضع ميلتون غرين حدًا أدنى لمتغير عدّ الـ1 في دالة القندس المشغول، ونُشر ذلك في وقائع ندوة IEEE لعام 1964 حول نظرية دوائر التحويل والتصميم المنطقي. وصف هاينر ماركسن ويورغن بونتروك هذا الحد بأنه «غير تافه (أي ليس أوليًا حسابيًا)». يمكن حساب هذا الحد الأدنى، لكنه معقد جدًا بحيث لا يمكن التعبير عنه بصيغة واحدة بدلالة n. تم هذا باستخدام مجموعة من آلات تورنغ، كل منها أظهر الحد الأدنى لقيمة معينة من n. عندما تكون n = 8 فإن الطريقة تعطي:
وعلى النقيض، فإن أفضل حد أدنى معروف حاليًا (حتى عام 2024) لـ  هو ، حيث تشير كل  إلى ترميز السهم لأب كنوث. ويمثل هذا ، سلسلة أُسية مكوّنة من 15 عشرة متتالية، تساوي . ومن المحتمل أن تكون قيمة  أكبر بكثير من ذلك.
القندس المشغول النتائج المعروفة
وقد تم إثبات هذا الحد الأدنى باستخدام سلسلة من آلات تورنغ العودية، كل واحدة منها تتكون من آلة أصغر مضاف إليها حالتان إضافيتان تطبّقان الآلة الأصغر مرارًا على شريط الإدخال. بتعريف قيمة متنافس القندس المشغول ذو N حالة على شريط يحتوي على  من الآحاد بأنها  (حيث الناتج النهائي لكل آلة يكون على  لأن الشريط الفارغ يحتوي على صفر من الآحاد)، فإن علاقات العودية هي كما يلي:
يؤدي هذا إلى صيغتين، للأعداد الفردية والزوجية، لحساب الحد الأدنى المعطى بواسطة الآلة رقم N، :
يمكن أيضًا ربط الحد الأدنى BB(N) بـ دالة أكرمان. ويمكن إثبات أن:
بديهياً، S(n) ≥ Σ(n) لأن الآلة التي تكتب Σ(n) واحدات يجب أن تأخذ على الأقل Σ(n) خطوة للقيام بذلك. من الممكن إعطاء عدة حدود عليا على الزمن S(n) بناءً على عدد الواحدات Σ(n):
بتعريف num(n) على أنه الحد الأقصى لعدد الواحدات التي يسمح لآلة تورينج ذات n حالة بطباعتها متتالية، بدلاً من في أي موضع (أي أكبر نظام عد أحادي يمكنها طباعته)، يمكن إثبات:
بن-أمرام وبيترسن، 2002، قدموا أيضاً حدًا محسنًا أسيمبتوتيًا لـ S(n). هناك ثابت c، بحيث لكل n ≥ 2:
القندس المشغول النتائج المعروفة
يعرض الجدول التالي القيم الدقيقة وبعض الحدود الدنيا المعروفة لـ S(n), Σ(n), وعدة دوال أخرى للبيزي بيفر. في هذا الجدول، تُستخدم آلات تورينج ذات رمزَين. الإدخالات المعلمة بعلامة "?" هي على الأقل بنفس حجم الإدخالات الموجودة على يسارها (لأن جميع الآلات ذات n حالة هي أيضاً آلات ذات (n+1) حالة)، وليست أكبر من الإدخالات التي فوقها (لأن S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)). لذا، من المعروف أن space(6) أكبر من 10⇈15، لأن space(n) ≥ Σ(n) وΣ(6) > 10⇈15. القيمة 47176870 هي حد علوي لـ space(5)، لأن S(5) = 47176870 () وS(n) ≥ space(n). العدد 4098 هو حد علوي لـ num(5)، لأن Σ(5) = 4098 () وΣ(n) ≥ num(n). الإدخال الأخير المعلم بـ "?" هو num(6)، لأن Σ(6) > 10⇈15، وΣ(n) ≥ num(n).
تم اكتشاف البيزي بيفر ذي الـ 5 حالات بواسطة هاينر ماركسن ويورغن بونتروك في 1989، ولكن لم يُثبت كونه الفائز بالمرتبة الخامسة — ويرمز له بـ BB(5) — إلا في 2024 باستخدام برهان في كووك.
هذه جداول قواعد لآلات تورينج التي تولد Σ(1) وS(1)، Σ(2) وS(2)، Σ(3) (لكن ليس S(3))، Σ(4) وS(4)، Σ(5) وS(5)، وأفضل حد أدنى معروف لـ Σ(6) وS(6).