القندس المشغول
المحتويات
- التعريف الفني
- الآلات تورنغ غير الحتمية
- تعميمات
- أعداد مختلفة من الرموز
- برهان على عدم قابلية S(n) وΣ(n) للحساب
- آلات تورنغ الشاملة
- أمثلة بارزة
- دالة النتيجة Σ
- الدوال
- مثال
- العلاقات بين دوال البيزي بيفر
- للأعداد الزوجية N
- اتساق النظريات
- دالة أقصى عدد من التحركات S
- القيم الدقيقة والحدود الدنيا والعليا
- التعقيد وعدم قابلية الإثبات لدالة Σ
- التصورات
- مسائل رياضية مفتوحة
- أطروحة تشرش–تورينغ الفيزيائية
- آلات غرين
- قائمة النماذج المشغولة
- عدم القابلية للحوسبة

قبل الخوض في التفاصيل، في علم الحاسوب النظري، تهدف لعبة القندس المشغول إلى إيجاد برنامج يتوقف ويكون (بحسب التعريف) إما أنه ينتج أكبر كمية ممكنة من الخرج، أو يعمل لأطول عدد ممكن من الخطوات. وبما أن بإمكان برنامجٍ ما أن يعمل إلى ما لا نهاية أو ينتج خرجًا لانهائيًا، فإن هذه البرامج تُستبعد من اللعبة. بدلًا من لغات البرمجة التقليدية، تُستعمل في اللعبة آلات تورنغ ذات n حالات، وهي من أوائل النماذج الرياضية للحوسبة. وفيما يلي تفاصيل أوسع عن ذلك.
من جهة ثانية، يُطلق على آلة تورنغ التي تفوز في لعبة القندس المشغول ذات n حالات اسم قندس مشغول-إن ، أو ببساطة "قندس مشغول"، وتُرمز إليها بـ بي بي-إن. بحسب التعريف، إما أن تُحقق هذه الآلة أعلى ناتج (ويرمز له بـ Σ(n) )، أو تعمل لأطول وقت (S(n))، مقارنةً بباقي الآلات المنافسة ذات n حالات.
ومن ناحية أخرى، تتكون آلات تورنغ من شريط لا نهائي، ومجموعة من الحالات المنتهية التي تعمل كـ"كود مصدر" للبرنامج. يُعرّف إنتاج أكبر ناتج بكونه كتابة أكبر عدد من الرقم 1 على الشريط، ويُعرف التشغيل الأطول بأنه تنفيذ أكبر عدد من الخطوات قبل التوقف. تتكوّن لعبة القندس المشغول ذات n حالات من إيجاد آلة تورنغ تتوقف وتُنتج أكبر ناتج أو تعمل لأطول وقت ممكن بين جميع الآلات الممكنة ذات n حالات. تُفترض هذه الآلات بأنها تبدأ على شريطٍ فارغ، يحتوي فقط على الأصفار والآحاد (آلة تورنغ ثنائية). هدف اللعبة هو برمجة مجموعة من الانتقالات بين الحالات لتحقيق أعلى ناتج أو أطول وقت تشغيل مع ضمان توقّف الآلة في النهاية.
وفي السياق ذاته، تحديد وقت التشغيل أو الناتج للـ n-قندس مشغول هو دالة غير قابلة للحساب. في الواقع، فإن كلا الدالتين Σ(n) وS(n) تتجاوزان في النهاية أي دالة قابلة للحساب. وهذا له تأثيرات على نظرية الحوسبة، ومسألة التوقف، ونظرية التعقيد الحسابي. تم تقديم مفهوم القندس المشغول لأول مرة بواسطة تيبور رادو في ورقته البحثية عام 1962 بعنوان "حول الدوال غير القابلة للحساب". ومن أكثر الجوانب إثارة في لعبة القندس المشغول أنه، لو كان بالإمكان حساب الدالتين Σ(n) وS(n) لكل n، لكان بالإمكان حينها حسم جميع التخمينات الرياضية التي يمكن ترميزها على شكل "هل تتوقف <هذه آلة تورنغ>". مثلًا، يمكن لآلة تورنغ ذات 27 حالة أن تتحقق من حدسية غولدباخ لكل عدد وتتوقف عند العثور على مثال مضاد: وإذا لم تتوقف هذه الآلة بعد تنفيذها S(27) خطوة، فإنها لا بد أن تعمل إلى الأبد، مما يحسم التخمين. ويمكن كذلك التعبير عن الكثير من المسائل الأخرى، بما في ذلك فرضية ريمان (744 حالة) واتساق نظرية المجموعات حسب تسيرميلو-فرانكل (745 حالة)، بطريقة مشابهة، حيث يمكن التحقق من عدد قابل للعد من الحالات على الأكثر.
التعريف الفني
علاوةً على ذلك، رمز لكتابته فوق الرمز في خلية الشريط الحالية (قد يكون هو نفسه الرمز الذي تتم الكتابة فوقه)،
الحالة الحالية غير حالة التوقف،
علاوةً على ذلك، تحتوي الآلة على n حالة "تشغيلية" فضلًا عن حالة توقف، حيث إن n عدد صحيح موجب، وتُعتبر إحدى حالات n هي الحالة الابتدائية. (عادةً ما تُرقّم الحالات 1، 2، ...، n، مع كون الحالة 1 هي الابتدائية، أو بالحروف A، B، C، ...، مع كون الحالة A هي الابتدائية.)
- تستعمل الآلة شريطًا لا نهائيًا (أو غير محدود) في كلا الاتجاهين.
- أبجدية الشريط هي {0، 1}، حيث تُستعمل 0 كرمز فراغ.
- تأخذ دالة الانتقال للآلة مدخلين:
حالة للانتقال إليها (قد تكون حالة التوقف).
من جانب آخر، لعبة القندس المشغول-إن (أو لعبة بي بي-إن)، التي قُدّمت في ورقة تيبور رادو عام 1962، تتعلق بفئة من آلة تورنغ، حيث يُطلب من كل عضو فيها أن يفي بالمواصفات التصميمية التالية:
وتُنتج ثلاث مخرجات:
كذلك، اتجاه للحركة (يسار أو يمين؛ أي الانتقال إلى خلية الشريط المجاورة إما لليسار أو اليمين من الخلية الحالية)،
الرمز في خلية الشريط الحالية،
من جهة ثانية، يتضمن "تشغيل" الآلة البدء من الحالة الابتدائية، مع اعتبار خلية الشريط الحالية هي أي خلية من شريط فارغ (كله أصفار)، ثم تكرار دالة الانتقال حتى الوصول إلى حالة التوقف (إن حدث ذلك). إذا، وفقط إذا، توقفت الآلة في النهاية، فإن عدد الآحاد المتبقية على الشريط يُسمى "نتيجة" الآلة. وبالتالي فإن لعبة البيفر المشغول ذات n حالات (BB-n) هي منافسة تهدف، حسب التعريف، إلى إيجاد آلة تورنغ بعدد n من الحالات تُنتج أعلى نتيجة ممكنة أو أطول وقت تشغيل.
الآلات تورنغ غير الحتمية
كذلك، يمكن توسيع المسألة لتشمل آلة تورنغ غير الحتمية من خلال البحث عن النظام الذي يحقق أكبر عدد من الحالات عبر جميع الفروع أو الفرع الذي يستغرق أكبر عدد من الخطوات. تظل مسألة ما إذا كانت آلة تورنغ غير الحتمية ستتوقف غير قابلة للاختزال حسابيًا، كما أن مقدار الحساب اللازم لإيجاد "القندس المشغول" لهذه الفئة أكبر بكثير مقارنة بالحالة الحتمية، إذ يجب أخذ عدة فروع في الاعتبار. بالنسبة لنظام بحالتين ولونين وp قاعدة أو حالة، يبين الجدول على اليمين الحد الأقصى لعدد الخطوات قبل التوقف وأقصى عدد من الحالات الفريدة التي تُنشئها الآلة.
التطبيقات
تعميمات
إضافةً إلى ذلك، وعليه، في فئة آلة تورنغ الانعكاسية (RTM)، فإن SRTM(6) ≥ وΣRTM(6) ≥ .
ومن جهة أخرى، يمكن تعريف نظائر لدالة الإزاحة ببساطة في أي لغة برمجة، بشرط أن يتم تمثيل البرامج كسلاسل من البتات، وأن يكون بالإمكان حساب عدد خطوات البرنامج.
إضافةً إلى ذلك، وبالمثل، يمكننا تعريف نظير لدالة Σ لآلات آلة السجل على أنه أكبر عدد يمكن أن يظهر في أي سجل عند التوقف، لعدد معين من التعليمات.
إضافةً إلى ذلك، وبدلاً من ذلك، يمكن تعريف "دالة القندس المشغول" لنماذج حوسبة مختلفة باستخدام تعقيد كولموغروف.
علاوةً على ذلك، أطول آلة تورنغ معروفة حتى الآن ذات 6 حالات ورمزين وتملك الخاصية الإضافية التي تقلب قيمة الشريط في كل خطوة، تنتج من الآحاد بعد خطوة.
وفي هذا السياق، فمثلًا، يمكن تعميم لعبة القندس المشغول إلى بعدين باستخدام آلات تورنغ تعمل على أشرطة ثنائية الأبعاد، أو آلات تورنغ يُسمح لها بالبقاء في نفس الموضع إلى جانب التحرك يمينًا ويسارًا.
علاوةً على ذلك، ويتم ذلك بأخذ ليكون أكبر عدد صحيح بحيث ، حيث هو طول أقصر برنامج في يقوم بإنتاج : وبهذا، فإن هو أكبر عدد صحيح يمكن لبرنامج بطول أو أقل أن ينتجه في .
أعداد مختلفة من الرموز
وعلى صعيد آخر، فمثلًا، آلة تورنغ ثلاثية الرموز m = 3 ستكون لديها الرموز 0، 1، و2.
من جهة ثانية، S(n, m): أكبر عدد من الخطوات التي يمكن أن تقوم بها آلة ذات n حالة وm رمزًا على شريط كان في البداية فارغًا، قبل أن تتوقف.
وفي هذا الصدد، Σ(n, m): أكبر عدد من الآحاد (أو القيم غير الصفرية) يمكن طباعته بواسطة آلة ذات n حالة وm رمزًا على شريط كان في البداية فارغًا، قبل أن تتوقف،
وفي السياق ذاته، مثلًا، أطول آلة ذات 3 حالات و3 رموز تم اكتشافها حتى الآن تقوم بـ خطوة قبل أن تتوقف.
في هذا الإطار، أحد التعميمات البسيطة هو التوسيع ليشمل آلات تورنغ التي تحتوي على m من الرموز بدلاً من مجرد رمزَين (0 و1).
في هذا الإطار، ويعرّف التعميم لآلات تورنغ التي تحتوي على n من الحالات وm من الرموز الدوال العامة التالية للقندس المشغول:
برهان على عدم قابلية S(n) وΣ(n) للحساب
وفي هذا السياق، كل من الدالتين و غير قابلتين للحساب. يمكن إثبات عدم قابلية حساب من خلال ملاحظة أن كل مربع على الشريط تكتب عليه آلة تورنغ الرقم واحد يجب أن تمر عليه كذلك؛ وبعبارة أخرى، .
وفي هذا السياق، كما يمكن إثبات عدم قابلية S(n) للحساب بالإشارة إلى مسألة التوقف على شريط فارغ، وهي المسألة التي تطرح ما إذا كانت آلة تورينغ ستتوقف عند تشغيلها على شريط فارغ. هذه المسألة مكافئة لـمسألة توقف القياسية، وبالتالي فهي كذلك غير قابلة للحساب. فإذا كانت S(n) قابلة للحساب، فبإمكاننا حل مسألة التوقف على شريط فارغ ببساطة عبر تشغيل أي آلة تورينغ مكونة من n حالة لمدة S(n) خطوة؛ فإذا لم تتوقف بعد، فلن تتوقف أبدًا. ونظرًا لأن مسألة التوقف غير قابلة للحساب، فإن S(n) لا بد أن تكون كذلك.
من جانب آخر، دع BadS هو تركيب الآلات: Create_n0 | دوبل | إيفالس | كلين. لاحظ أن هذه الآلة تحتوي على N حالة. تبدأ بشريط فارغ، فتُنشئ أولًا سلسلة من n0 من الآحاد، ثم تُضاعفها إلى سلسلة من N من الآحاد. فيما بعد تُنتج S(N) من الآحاد، وأخيرًا تمسح الشريط وتتوقف. لكن مرحلة المسح تستغرق على الأقل S(N) خطوة، مما يعني أن زمن عمل BadS يفوق S(N)، وهو ما يتعارض مع تعريف الدالة S(n).
وفي السياق ذاته، افترض أن S(n) دالة قابلة للحساب، ولنرمز إلى آلة تورينغ التي تحسبها بـ إيفالس. عند إعطائها شريطًا يحتوي على n من الآحاد، ستنتج S(n) من الآحاد على الشريط ثم تتوقف. ولنُعرّف آلة كلين بأنها آلة تورينغ تنظف سلسلة الآحاد المكتوبة في البداية. ولنُعرّف آلة دوبل بأنها آلة تورينغ تحسب الدالة n + n، أي أنها تنتج 2n من الآحاد ثم تتوقف. لنُنشئ الآن التركيب التالي: دوبل | إيفالس | كلين، ولنفرض أن عدد حالات هذه الآلة هو n0. ولندع Create_n0 آلة تورينغ تُنشئ n0 من الآحاد على شريط فارغ، ويمكن بناء هذه الآلة بشكل بسيط بحيث تحتوي على n0 حالة (تقوم الحالة i بكتابة 1، ثم تحرك الرأس يمينًا وتنتقل إلى الحالة i + 1، ما عدا الحالة الأخيرة التي تتوقف). ولنُعرّف N بأنه المجموع: n0 + n0.
عدم قابلية حساب الدالتين سبيس(n) ونوم(n)
إضافةً إلى ذلك، ويمكن إثبات عدم قابلية Σ(n) للحساب بطريقة مماثلة. في البرهان أعلاه، يُستبدل إيفالس بـ إيفالΣ، وكلين بـ إنكريمينت — وهي آلة تورينغ بسيطة تبحث عن أول 0 على الشريط وتستبدله بـ 1.
ومن ناحية أخرى، أما بالنسبة لدالة ، فيمكن إثبات عدم قابليتها للحساب، مثلًا، من خلال إثبات أن ، ويتم ذلك عن طريق تصميم آلة تورنغ ذات "(3n+3)" حالة تقوم بمحاكاة آلة تورنغ ذات n حالة التي تمثل البطل في استهلاك المساحة، وتستعملها لكتابة ما لا يقل عن من الآحاد المتجاورة على الشريط.
آلات تورنغ الشاملة
من جهة ثانية، أثناء استكشاف العلاقة بين الشمولية الحاسوبية والسلوك الديناميكي لآلات تورنغ من نوع "القندس المشغول"، تم اقتراح تخمين في سنة 2012 يفترض أن آلات "القندس المشغول" هي مرشح طبيعي للشمولية التورنجية لأنها تُظهر خصائص معقدة، تُعرف بـ (1) تعقيدها الحسابي الأقصى ضمن قيود الحجم، (2) قدرتها على إجراء حسابات غير تافهة قبل التوقف، و(3) صعوبة العثور عليها وإثبات خصائصها؛ وهذه الخصائص تشير إلى أن هذه الآلات تمتلك التعقيد اللازم لتحقيق الشمولية.
أمثلة بارزة
وعلى صعيد آخر، تم بناء آلة تورنغ بعدد 744 حالة تتوقف إذا وفقط إذا كانت فرضية ريمان خاطئة.
وفي هذا السياق، تم بناء آلة تورنغ بعدد 15 حالة تتوقف إذا وفقط إذا كانت التخمينية التالية التي صاغها بول إيردوش سنة 1979 خاطئة: لكل عدد n > 8، يوجد على الأقل رقم 2 واحد في تمثيل العدد 2n في الأساس الثلاثي.
ومن جهة أخرى، تم بناء آلة تورنغ بعدد 43 حالة تتوقف إذا وفقط إذا كانت حدسية غولدباخ خاطئة. ثم جرى تقليل ذلك إلى آلة ذات 25 حالة، ولاحقًا تم إثباتها والتحقق منها رسميًا باستخدام لغة إثبات النظريات لين 4.
من جانب آخر، تم بناء آلة تورنغ ثنائية بعدد 745 حالة تتوقف إذا وفقط إذا كانت نظرية المجموعات حسب تسيرميلو-فرانكل غير متسقة.
دالة النتيجة Σ
في هذا الإطار، تُعرَّف دالة النتيجة بحيث تكون Σ(n) هي الحد الأقصى الممكن للنتيجة (أي أكبر عدد من الرموز 1 المتبقية على الشريط في النهاية) بين جميع آلات تورنغ المتوقفة المكونة من n حالة ورمزين كما تم وصفها أعلاه، عند بدء تشغيلها على شريط فارغ.
علاوةً على ذلك، بحسب تعريف النتيجة، فإن أي آلة تورنغ مكونة من n حالة ورمزين تُسمى "قندسًا مشغولًا" إذا كانت (أي إذا بلغت النتيجة القصوى). ولكل قيمة n، يوجد على الأقل 4(n − 1)! من "القنادس المشغولة" ذات n حالة. (فعند وجود آلة من هذا النوع، يمكن الحصول على أخرى بمجرد تغيير اتجاه الانتقال في خطوة الإيقاف، وثالثة بعكس **كل** اتجاهات الانتقال بشكل موحد، ورابعة بعكس اتجاه الإيقاف في "القندس" المعدل بالكامل. علاوة على ذلك، فإن تبديل ترتيب كل الحالات ما عدا الابتداء والتوقف يُنتج آلة تُحقق نفس النتيجة. من الناحية النظرية، يمكن أن توجد أكثر من عملية انتقال واحدة تؤدي إلى حالة التوقف، لكن في الممارسة سيكون ذلك غير فعّال، لأنه لا توجد سوى سلسلة واحدة من الانتقالات تؤدي إلى النتيجة المطلوبة.)
علاوةً على ذلك، تقيس دالة النتيجة الحد الأقصى للنتيجة التي يمكن أن يحققها "القندس المشغول" بحسب مقياس معين. وتُعد هذه دالة حسوبة، لأنها تنمو وفق تحليل مقارب أسرع من أي دالة قابلة للحوسبة.
من جانب آخر، ومن الواضح أن Σ دالة معرفة جيدًا: لكل n يوجد عدد منتهي (بحد أقصى) من آلات تورنغ ذات n حالة كما سبق، حتى حد التماثل البنيوي، وبالتالي فإن عدد أوقات التشغيل المحتملة كذلك منتهٍ.
الدوال
في هذا الإطار، تُعرّف الدالة بأنها أقصى عدد من الآحاد المتجاورة يمكن أن تكتبها آلة تورنغ تتوقف على شريط فارغ. بعبارة أخرى، هذا هو أكبر نظام عد أحادي يمكن أن تكتبه آلة تورنغ ذات n حالة على الشريط.
من جهة ثانية، في ورقته الأصلية عام 1962، عرّف رادو دالتين تتعلقان بلعبة البيفر المشغول: دالة النتيجة Σ(n) ودالة الحركات S(n). كلتاهما تأخذ عددًا معينًا من حالات آلة تورنغ وتُنتجان أعلى نتيجة ممكنة لآلة تورنغ بذلك العدد من الحالات حسب مقياس معين. تُعطي دالة النتيجة Σ(n) أكبر عدد من الآحاد يمكن أن تُنتجه آلة تورنغ ذات n حالة قبل التوقف، بينما تُعطي دالة الحركات S(n) أكبر عدد من الحركات (أو الخطوات، لأن كل خطوة تتضمن حركة) يمكن أن تقوم بها آلة تورنغ قبل التوقف. وقد أثبت أن كلتا الدالتين هما دالة غير قابلة للحساب، لأن كلًا منهما تنمو أسرع من أي دالة قابلة للحساب. تم تعريف الدالة بي بي-إن لتكون أيًا من هاتين الدالتين، لذا لا يُستعمل هذا الترميز في هذه المقالة.
وفي هذا السياق، يمكن كذلك تعريف عدد من الدوال غير القابلة للحساب بناءً على قياس أداء آلات تورنغ بطرق أخرى غير الوقت أو عدد الآحاد الأقصى. مثلًا:
من جانب آخر، ترتبط هذه الدوال الأربع بالعلاقة . يمكن كذلك تعريف المزيد من الدوال من خلال تشغيل اللعبة على آلات حسابية مختلفة، مثل آلات تورنغ ذات ثلاثة رموز، أو آلات تورنغ غير حتمية، أو التكامل لامدا أو حتى لغات برمجة عشوائية.
من جانب آخر، تُعرّف الدالة بأنها أكبر عدد من خلايا الشريط يمكن لآلة تورنغ تتوقف أن تقرأها (أي تزورها) قبل التوقف. يشمل ذلك الخلية الابتدائية، لكن لا يشمل الخلية التي تصل إليها الآلة فقط بعد انتقال التوقف (إذا كان انتقال التوقف مُحددًا باتجاه حركة)، لأن هذه الخلية لا تؤثر في سلوك الآلة. تمثل هذه الدالة الحد الأقصى لتعقيد المساحة لآلة تورنغ ذات n حالة.
مثال
قد تكون قواعد آلة تورنغ ذات حالة واحدة كالتالي:
وفي هذا السياق، في الحالة 1، إذا كان الرمز الحالي 1، اكتب 0، وتحرك خانة واحدة إلى اليمين، وانتقل إلى التوقف (HALT)
وفي السياق ذاته، في الحالة 1، إذا كان الرمز الحالي 0، اكتب 1، وتحرك خانة واحدة إلى اليمين، وانتقل إلى الحالة 1
ومن ناحية أخرى، تقوم هذه الآلة بالتحرك إلى اليمين وتبديل قيمة جميع الخلايا التي تمر بها. وبما أن الشريط الابتدائي كله أصفار، فإنها ستُنتج سلسلة لا نهائية من الآحاد. هذه الآلة لا تُعتبر مرشحة للبيفر المشغول لأنها تعمل إلى ما لا نهاية على شريط فارغ.
العلاقات بين دوال البيزي بيفر
كذلك، بديهياً، S(n) ≥ Σ(n) لأن الآلة التي تكتب Σ(n) واحدات يجب أن تأخذ على الأقل Σ(n) خطوة للقيام بذلك. من الممكن إعطاء عدة حدود عليا على الزمن S(n) بناءً على عدد الواحدات Σ(n):
إضافةً إلى ذلك، بن-أمرام وبيترسن، 2002، قدموا كذلك حدًا محسنًا أسيمبتوتيًا لـ S(n). هناك ثابت c، بحيث لكل :
(بن-أمرام وآخرون، 1996)
من جهة ثانية، بتعريف num(n) على أنه الحد الأقصى لعدد الواحدات التي يسمح لآلة تورينج ذات n حالة بطباعتها متتالية، بدلاً من في أي موضع (أي أكبر نظام عد أحادي يمكنها طباعته)، يمكن إثبات:
- (رادو)
- (بورو)
- (بن-أمرام، جولستروم وزويك)
للأعداد الزوجية N
وفي هذا الصدد، يمكن كذلك ربط الحد الأدنى BB(N) بـ دالة أكرمان. ويمكن إثبات أن:
اتساق النظريات
علاوةً على ذلك، من الخصائص الأخرى للدالة S(n) أن أي نظرية منطقية حسابيًا سليمة ومؤكسمة حسابيًا لا يمكنها إثبات جميع قيم هذه الدالة. على وجه التحديد، إذا كانت لدينا نظرية قابلة للحساب وسليمة حسابيًا ، فهناك عدد بحيث لا يمكن إثبات أي عبارة من الشكل في لكل . وهذا يعني أن لكل نظرية هناك قيمة قصوى محددة لـ S(n) يمكنها إثباتها. ويعود السبب في ذلك إلى أنه يمكن تصميم آلة تورنغ بعدد من الحالات لتقوم بتعداد جميع الإثباتات الممكنة في . وإذا كانت النظرية غير متسقة، فإن جميع العبارات الخاطئة تصبح قابلة للإثبات، ويمكن إعطاء آلة تورنغ شرط التوقف فقط إذا وجدت إثباتًا لعبارة مثل . أي نظرية تثبت قيمة تكون قد أثبتت اتساقها الداخلي، مما ينتهك مبرهنات عدم الاكتمال لغودل. يمكن استخدام هذه الخاصية لترتيب النظريات على سلم، مثلًا بديهيات الكرديناليات الكبيرة في نظرية المجموعات حسب تسيرميلو-فرانكل: إذا أُسند لكل نظرية العدد ، فإن النظريات ذات القيم الأعلى لـ تثبت اتساق النظريات ذات القيم الأدنى، مما يضع كل هذه النظريات على سلم قابل للعد لا نهائي.
دالة أقصى عدد من التحركات S
وفي السياق ذاته، نظرًا لأن آلات تورينغ العادية يُشترط أن تُجري تحركًا في كل انتقال أو "خطوة" (بما في ذلك الانتقال إلى الحالة النهائية Halt)، فإن دالة أقصى عدد من التحركات هي في الوقت ذاته دالة أقصى عدد من الخطوات.
في هذا الإطار، فضلًا عن الدالة Σ، قدّم رادو [1962] دالة قصوى أخرى للآلات التورينغ تُعرف باسم دالة أقصى عدد من التحركات، 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 خطوة.
عدد التحركات التي يُجريها M قبل التوقف، لأي ،
في هذا الإطار، في سنة 2016، حصل آدم يديديا وسكوت آرنسون على أول حد علوي (صريح) لأصغر قيمة لـ n بحيث تكون قيمة S(n) غير قابلة للإثبات ضمن نظرية المجموعات حسب تسيرميلو-فرانكل. للقيام بذلك، أنشأوا آلة تورينغ مكونة من 7910 حالة لا يمكن إثبات سلوكها بناءً على بديهيات نظرية المجموعات الشائعة (نظرية المجموعات حسب تسيرميلو-فرانكل مع بديهية الاختيار), بافتراض فرضيات اتساق معقولة (خاصية رامزي الثابتة). لاحقًا خفّض ستيفان أورير عدد الحالات إلى 1919، مع إزالة الاعتماد على خاصية رامزي الثابتة، ثم إلى 748 حالة. وفي يوليو 2023، خفّض رايبل العدد إلى 745 حالة.
من جانب آخر، أكبر عدد من التحركات التي تُجريها أي آلة تورينغ تتوقف من نوع "n حالة و2 رمزًا".
في هذا الإطار، وقد بيّن رادو أن S غير قابلة للحساب لنفس السبب الذي يجعل Σ غير قابلة للحساب — فهي تنمو أسرع من أي دالة قابلة للحساب. وقد أثبت ذلك ببساطة من خلال ملاحظة أنه لكل n، فإن S(n) ≥ Σ(n). إذ إن كل تحرك قد يكتب 0 أو 1 على الشريط، في حين أن Σ تعد مجموعة فرعية من التحركات التي كتبت 1، وتحديدًا تلك التي لم تُكتب فوقها بحلول وقت توقف الآلة؛ وبالتالي، فإن S تنمو على الأقل بالسرعة نفسها التي تنمو بها Σ، والتي سبق أن ثبت أنها تنمو أسرع من أي دالة قابلة للحساب.
القيم الدقيقة والحدود الدنيا والعليا
من جانب آخر، يعرض الجدول التالي القيم الدقيقة وبعض الحدود الدنيا المعروفة لـ 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).
في هذا الإطار، تم اكتشاف البيزي بيفر ذي الـ 5 حالات بواسطة هاينر ماركسن ويورغن بونتروك في 1989، ولكن لم يُثبت كونه الفائز بالمرتبة الخامسة — ويرمز له بـ BB(5) — إلا في 2024 باستخدام برهان في كووك.
التعقيد وعدم قابلية الإثبات لدالة Σ
من جهة ثانية، يُعرَّف نوع مختلف من تعقيد كولموغروف كما يلي: يُعرّف "تعقيد" عدد n بأنه أقل عدد من الحالات اللازمة لآلة تورنغ من فئة القندس المشغول تتوقف بعد أن تكتب كتلة واحدة من n رموز متتالية من الرقم 1 على شريط فارغ. وبحسب النوع المكافئ من تعقيد كولموغروف، فإنه في سياق نظام بديهيات معين للأعداد الطبيعية، يوجد عدد k لا يمكن إثبات أن أي عدد معين يمتلك تعقيدًا أكبر منه، وبالتالي لا يمكن إثبات أي حد أعلى محدد لـΣ(k) (لأن إثبات أن "تعقيد n أكبر من k" يستلزم إثبات أن ). وكما ورد في المرجع المشار إليه، فإن أقل قيمة لـk ينطبق عليها هذا الكلام في أي نظام بديهي لـ"الرياضيات العادية" هي أقل بكثير من 10⇈10؛ ونتيجة لذلك، لا يمكن في سياق الرياضيات العادية إثبات قيمة Σ(10⇈10) أو أي حد أعلى لها. (مبرهنات عدم الاكتمال لغودل تتضح من خلال هذه النتيجة: ففي نظام بديهي للرياضيات العادية، توجد جملة صحيحة ولكن غير قابلة للإثبات من الشكل ، كما توجد عدد لا نهائي من الجمل الصحيحة ولكن غير القابلة للإثبات من الشكل .)
التصورات
الملاحظات
كذلك، في الجدول التالي، تمثَّلت قواعد كل "بيزبيفر" (المُعظِّم لـ Σ) بصريًا، حيث تمثل المربعات البرتقالية الرقم "1" على الشريط، واللون الأبيض يمثل الرقم "0". يتم الإشارة إلى موقع الرأس بواسطة شكل بيضاوي أسود، مع تمثيل اتجاه الرأس للحالة الحالية. يتم عرض الشرائط بشكل أفقي، ويتقدم الزمن من الأعلى إلى الأسفل. تمثل حالة التوقف قاعدة تُطابق حالة واحدة مع نفسها (أي أن الرأس لا يتحرك).
مسائل رياضية مفتوحة
وفي هذا السياق، من الصعب جدًا إثبات قيم دالة القندس المشغول (ودالة الإزاحة القصوى). فقد تم إثبات كل قيمة معروفة لـ S(n) عن طريق تعداد جميع آلات تورنغ ذات n حالة وإثبات ما إذا كانت تتوقف أم لا. لا بد من إيجاد طريقة غير مباشرة لحساب S(n) كي تصبح مفيدة حقًا.
في هذا الإطار، الآن، لنفترض أن هذا البرنامج يُحاكى باستخدام آلة تورنغ ذات n حالة، وإذا كنا نعرف S(n), يمكننا أن نقرر (في وقت محدود) ما إذا كانت هذه الآلة ستتوقف في النهاية أم لا عبر تشغيلها حتى S(n) خطوة. فإذا لم تتوقف الآلة فيما بعد، نعلم أنها لن تتوقف أبدًا، وبالتالي نعلم أنه لا توجد أمثلة معاكسة للحدسية المعطاة (أي، لا توجد أعداد زوجية لا يمكن كتابتها كمجموع عددين أوليين). هذا سيُعد برهانًا لصحة الحدسية. وبالتالي يمكن، نظريًا، استخدام قيم محددة (أو حدود عُليا) لـ S(n) لحل الكثير من المسائل المفتوحة في الرياضيات بشكل منهجي.
من جانب آخر، لكن، تشير النتائج الحالية المتعلقة بمسألة القندس المشغول إلى أن ذلك غير عملي لسببين:
علاوةً على ذلك، قيم S(n) ودوال القندس المشغول الأخرى تزداد بشكل هائل وسريع جدًا. فمثلًا، قيمة S(5) تبلغ قرابة 47 مليون فقط، بينما قيمة S(6) تتجاوز 10⇈15، أي مع 15 عدد 10 متراكبًا. هذا الرقم يحتوي على 10⇈14 رقمًا وهو رقم غير عملي تمامًا للاستخدام في الحسابات. أما قيمة S(27)، وهي عدد الخطوات الذي يتعين على البرنامج الحالي لاختبار حدسية غولدباخ تشغيله لتقديم إجابة قاطعة، فهي هائلة بشكل يفوق الفهم، وغير قابلة للتسجيل أو التنفيذ حتى داخل الكون المرئي.
علاوةً على ذلك، تأمل أي حدسية من نوع ، أي حدسية يمكن إثباتها رياضيًا بواسطة مثال معاكس ضمن مجموعة قابلة للعد من الحالات، مثل حدسية غولدباخ. اكتب برنامج حاسوب يتحقق من صحة هذه الحدسية بالتسلسل لقيم متزايدة. في مثال حدسية غولدباخ، سنفحص كل عدد زوجي ≥ 4 ونتحقق مما إذا كان يمكن كتابته كمجموع عددين أوليين. إذا وجد البرنامج مثالًا معاكسًا (عدد زوجي ≥ 4 لا يمكن كتابته كمجموع عددين أوليين)، سيتوقف ويُشير إلى ذلك. أما إذا كانت الحدسية صحيحة، فلن يتوقف البرنامج أبدًا. (يتوقف البرنامج فقط إذا وجد مثالًا معاكسًا).
كذلك، إضافةً إلى كونها لعبة رياضية صعبة، توفر دوال القندس المشغول Σ(n) وS(n) مدخلًا جديدًا تمامًا لحل مسائل الرياضيات البحتة. فمن الناحية النظرية، يمكن حل الكثير من قائمة المسائل غير المحلولة في الرياضيات بشكل منهجي إذا ما توفرت قيمة S(n) لعدد كافٍ من الحالات. فمبدئيًا، تحتوي قيمة S(n) على إجابات جميع الحدسيات الرياضية التي يمكن التحقق منها في وقت غير محدود باستخدام آلة تورنغ لا تتجاوز n حالة.
أطروحة تشرش–تورينغ الفيزيائية
النتائج المعروفة
وعلى صعيد آخر، تمتلك خصائص نمو دالة "القندس المشغول" تبعات على سلوك الأنظمة الفيزيائية، بافتراض صحة أطروحة تشرش-تورينغ. فإذا كانت هذه الأطروحة الفيزيائية صحيحة، وكل الدوال القابلة للحوسبة فيزيائيًا قابلة للحوسبة بواسطة آلة تورنغ، فإنه لا يمكن لأي كمية فيزيائية قابلة للقياس المباشر أن تنمو أسرع من دالة "القندس المشغول"، لأن أي دالة قابلة للحوسبة بواسطة آلة تورنغ لا يمكن أن تنمو أسرع منها. كما أن الدوال البسيطة المرتبطة بـ تفرض كذلك حدًا أدنى على معدلات النمو، إلى جانب حدود عليا وسفلى على معدلات التقارب.
الحدود الدنيا
آلات غرين
في هذا الإطار، في عام 1964، وضع ميلتون غرين حدًا أدنى لمتغير عدّ الـ1 في دالة القندس المشغول، ونُشر ذلك في وقائع ندوة IEEE لعام 1964 حول نظرية دوائر التحويل والتصميم المنطقي. وصف هاينر ماركسن ويورغن بونتروك هذا الحد بأنه «غير تافه (أي ليس أوليًا حسابيًا)». يمكن حساب هذا الحد الأدنى، لكنه معقد جدًا بحيث لا يمكن التعبير عنه بصيغة واحدة بدلالة n. تم هذا باستخدام مجموعة من آلات تورنغ، كل منها أظهر الحد الأدنى لقيمة معينة من n. عندما تكون n = 8 فإن الطريقة تعطي:
من جانب آخر، وقد تم إثبات هذا الحد الأدنى باستخدام سلسلة من آلات تورنغ العودية، كل واحدة منها تتكون من آلة أصغر مضاف إليها حالتان إضافيتان تطبّقان الآلة الأصغر مرارًا على شريط الإدخال. بتعريف قيمة متنافس القندس المشغول ذو N حالة على شريط يحتوي على من الآحاد بأنها (حيث الناتج النهائي لكل آلة يكون على لأن الشريط الفارغ يحتوي على صفر من الآحاد)، فإن علاقات العودية هي كما يلي:
من جانب آخر، يؤدي هذا إلى صيغتين، للأعداد الفردية والزوجية، لحساب الحد الأدنى المعطى بواسطة الآلة رقم N، :
.
من جهة ثانية، وعلى النقيض، فإن أفضل حد أدنى معروف في الوقت الحالي (حتى عام 2024) لـ هو ، حيث تشير كل إلى ترميز السهم لأب كنوث. ويمثل هذا ، سلسلة أُسية مكوّنة من 15 عشرة متتالية، تساوي . ومن المحتمل أن تكون قيمة أكبر بكثير من ذلك.
للأعداد الفردية N
قائمة النماذج المشغولة
من جانب آخر، هذا واحد من عدة آلات غير مكافئة تعطي ستة 1s. بخلاف الآلات السابقة، هذه هي نشيطة للتابع Σ، لكنها ليست كذلك لـS. (S(3) = 21، وهذه الآلة تحصل فقط على خمسة 1s.)
- مفتاح النتيجة: (تبدأ عند الموقع ، وتتوقف عند الموقع )
- النتيجة: 0 0 0 (خطوة واحدة، واحد "1" إجمالًا)
- النتيجة: 0 0 1 1 1 0 0 (6 خطوات، أربعة "1" إجمالًا)
- النتيجة: 0 0 1 1 1 1 0 0 (14 خطوة، ستة "1" إجمالًا).
من جهة ثانية، تبدأ كل آلة في الحالة A مع شريط لا نهائي يحتوي على أصفار فقط. لذا، الرمز الأول المقروء هو 0.
النتيجة: 4098 "1" مع 8191 "0" موزعة خلال 47,176,870 خطوة.
ومن ناحية أخرى، النتيجة: 1 1 1 1 ... 1 1 1 ("10" متبوعة بأكثر من 10↑↑15 رقم واحد متتالي في أكثر من 10↑↑15 خطوة، حيث 10↑↑15=1010..10، وهو برج أُسّي مكوّن من 15 عشرة).
ومن جهة أخرى، لاحظ في الصورة إلى اليمين كيف أن هذا الحل يشبه نوعيًا تطور بعض مصفوفة خلايا ذاتية التشغيل.
كذلك، في الجداول، تمثل الأعمدة الحالة الحالية وتمثل الصفوف الرمز الحالي المقروء من الشريط. كل خانة في الجدول هي سلسلة من ثلاثة أحرف، تشير إلى الرمز الذي يُكتب على الشريط، والاتجاه الذي يتحرك إليه الرأس، والحالة الجديدة (بالترتيب). حالة التوقف تُعرض كـ H.
ومن ناحية أخرى، هذه جداول قواعد لآلات تورينج التي تولد Σ(1) وS(1)، Σ(2) وS(2)، Σ(3) (لكن ليس S(3))، Σ(4) وS(4)، Σ(5) وS(5)، وأفضل حد أدنى معروف لـ Σ(6) وS(6).
وعلى صعيد آخر، النتيجة: 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 خطوات، ثلاثة عشر "1" إجمالًا)
عدم القابلية للحوسبة
إضافةً إلى ذلك، وعليه، فإن هذا يُفضي إلى أن مسألة تحديد ما إذا كانت آلة تورنغ معينة "قندسًا مشغولًا" هي معضلة غير قابلة للقرار عبر أي خوارزمية عامة. (إذ لا يمكن أن توجد خوارزمية كهذه، لأن وجودها سيؤدي إلى إمكانية حساب Σ، وهو أمر مستحيل حسب الإثبات السابق. وبالتحديد، يمكن استخدام هذه الخوارزمية لتصميم خوارزمية أخرى تحسب Σ كما يلي: لأي n مُعطى، يتم اختبار جميع آلات تورنغ ذات n حالة ورمزين (وعددها منتهٍ) إلى أن يتم العثور على "قندس مشغول"، ثم تُحاكى هذه الآلة لحساب نتيجتها، والتي تُساوي بحكم التعريف Σ(n).)
في هذا الإطار، أثبت رادو في ورقته عام 1962 أن إذا كانت أي دالة حسوبة، فإن Σ(n) > f(n) لكل قيم n الكبيرة بما فيه الكفاية، ومن ثم فإن Σ دالة غير قابلة للحوسبة.
في هذا الإطار، على الرغم من أن Σ(n) دالة غير قابلة للحوسبة، إلا أنه من الممكن حساب قيمها وإثبات صحتها لبعض القيم الصغيرة لـn. ومن السهل إظهار أن Σ(0) = 0، Σ(1) = 1، Σ(2) = 4، وبمزيد من الجهد يمكن إثبات أن Σ(3) = 6، Σ(4) = 13، وΣ(5) = 4098 . ولم يتم حتى الآن تحديد Σ(n) لأي قيمة n > 5، رغم أنه قد تم إثبات بعض الحدود الدنيا لها (انظر قسم القيم المعروفة أدناه).
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟