مشكلة التوقف

قد تكون بعض الحلقات اللانهائية مفيدة للغاية. على سبيل المثال، تُبرمج حلقات الأحداث عادةً على شكل حلقات لانهائية. ^{[ 5 ]} ومع ذلك، فإن معظم الإجراءات الفرعية مصممة للانتهاء. ^{[ 6 ]}

في الحوسبة ذات الوقت الحقيقي الصارم ، لا يكفي أن تنتهي الإجراءات الفرعية فحسب، بل يجب أن تنتهي قبل الموعد النهائي المحدد. ^{[ 7 ]} ولتحقيق هذه المتطلبات، يطبق المبرمجون قاعدة أقل استهلاك للطاقة ويستخدمون أساليب محدودة، ليست كاملة تمامًا من حيث قدرة تورينج، مما يسهل إثبات أن الإجراءات الفرعية الناتجة تنتهي قبل الموعد النهائي المحدد. وتشمل هذه اللغات لغات مثل MISRA C و SPARK و Rocq .

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

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

تُعدّ مشكلة التوقف قابلة للحل بالنسبة للآلات الخطية المحدودة (LBAs) أو الآلات الحتمية ذات الذاكرة المحدودة. تمتلك هذه الآلة عددًا محدودًا من التكوينات الممكنة، لذا فإن أي برنامج حتمي عليها يجب أن يتوقف في النهاية أو يُعيد تكوينًا سابقًا: ^{[ 8 ]}

... أي آلة ذات حالات محدودة، إذا تُركت دون تدخل، ستدخل في نهاية المطاف في نمط دوري متكرر تمامًا . ولا يمكن أن تتجاوز مدة هذا النمط المتكرر عدد الحالات الداخلية للآلة...

ومع ذلك، يشير مينسكي إلى ما يلي: ^{[ 9 ]}

...إن المقادير المعنية ينبغي أن تدفع المرء إلى الشك في أن النظريات والحجج القائمة أساسًا على مجرد محدودية مخطط الحالة قد لا تحمل قدرًا كبيرًا من الأهمية.

على سبيل المثال، سيكون لدى جهاز كمبيوتر يحتوي على مليون مكون ثنائي الحالة ما لا يقل عن ^21,000,000 حالة ممكنة: ^{[ 9 ]}

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

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

• 1900  ( 1900 ) : طرح ديفيد هيلبرت "أسئلته الـ 23" (المعروفة الآن باسم مسائل هيلبرت ) في المؤتمر الدولي الثاني للرياضيات في باريس. "وكان السؤال الثاني من بينها هو إثبات اتساق " مسلمات بيانو " التي، كما بيّن، تعتمد عليها دقة الرياضيات". ^{[ 10 ]}
• 1920  ( 1920 )  - 1921  ( 1921 ) : استكشف إميل بوست مشكلة التوقف لأنظمة الوسوم ، معتبرًا إياها مرشحة لعدم إمكانية حلها. ^{[ 11 ]} لم يتم إثبات عدم إمكانية حلها إلا بعد ذلك بكثير، على يد مارفن مينسكي . ^{[ 12 ]}
•  في عام ١٩٢٨ ، أعاد هيلبرت صياغة "مشكلته الثانية" في مؤتمر بولونيا الدولي. ^{[ ١٣ ]} طرح ثلاثة أسئلة: ١- هل الرياضيات كاملة ؟ ٢- هل الرياضيات متسقة ؟ ٣- هل الرياضيات قابلة للتقرير ؟ ^{[ ١٤ ]} يُعرف السؤال الثالث باسم " مشكلة القرار ". ^{[ ١٥ ]}
• ١٩٣٠  : أعلن كورت غودل عن برهانٍ كإجابةٍ على السؤالين الأولين من أسئلة هيلبرت عام ١٩٢٨. ^{[ ١٦} ] "في البداية ، كان [هيلبرت] غاضبًا ومحبطًا، لكنه بدأ بعد ذلك في محاولة التعامل مع المشكلة بشكلٍ بنّاء... شعر غودل نفسه - وعبر عن هذه الفكرة في بحثه - أن عمله لا يتعارض ^مع وجهة نظر هيلبرت الشكلية". ^{[ ١٧ ]}
• 1931  ( 1931 ) : نشر غودل "حول القضايا غير القابلة للتقرير رسميًا في كتاب Principia Mathematica والأنظمة ذات الصلة I". ^{[ 18 ]}
• 19  أبريل  1935  ( 1935-04-19 ) : نشر ألونسو تشيرش بحثًا بعنوان "مسألة غير قابلة للحل في نظرية الأعداد الأولية"، يقترح فيه إمكانية صياغة المفهوم البديهي للدالة القابلة للحساب فعليًا باستخدام الدوال التكرارية العامة ، أو بشكل مكافئ باستخدام الدوال القابلة للتعريف باستخدام دالة لامدا . وقد أثبت أن مسألة التوقف في حساب لامدا (أي ما إذا كان لتعبير لامدا معين شكل طبيعي ) غير قابلة للحساب فعليًا. ^{[ 19 ]}
• 1936  ( 1936 ) : نشر تشرش أول برهان على أن مسألة القرار غير قابلة للحل، باستخدام مفهوم الحساب بواسطة الدوال المتكررة . ^{[ 20 ]}
• 7  أكتوبر  1936  ( 1936-10-07 ) : تم استلام ورقة إميل بوست بعنوان "العمليات التوافقية المحدودة. الصياغة 1". أضاف بوست إلى "عمليته" تعليمات "(ج) توقف". أطلق على هذه العملية اسم "النوع 1 ... إذا كانت العملية التي تحددها تنتهي لكل مسألة محددة." ^{[ 21 ]}
• مايو  1936  ( 1936-05 )  - يناير  1937  ( 1937-01 ) : نُشرت ورقة آلان تورينج البحثية بعنوان "حول الأعداد القابلة للحساب مع تطبيق على مسألة القرار" في مايو 1936، ووصلت إلى الطباعة في يناير 1937. ^{[ 22 ]} أثبت تورينج أن ثلاث مسائل غير قابلة للحل: مسألة "الإرضاء"، ومسألة "الطباعة"، ومسألة القرار . ^{[ 23 ]} يختلف برهان تورينج عن برهان تشرش بإدخاله مفهوم الحساب بواسطة الآلة. يُعد هذا أحد "الأمثلة الأولى لمسائل القرار التي ثبت عدم قابليتها للحل". ^{[ 24 ]}
• 1939  ( 1939 ) : لاحظ ج. باركلي روسر التكافؤ الجوهري لـ "الطريقة الفعالة" التي حددها غودل وتشرش وتورينغ. ^{[ 25 ]}
• 1943  ( 1943 ) : في ورقة بحثية، ذكر ستيفن كلين أنه "عند وضع نظرية خوارزمية كاملة، فإن ما نقوم به هو وصف إجراء ... ينتهي هذا الإجراء بالضرورة وبطريقة تمكننا من قراءة إجابة محددة من النتيجة، 'نعم' أو 'لا'، على السؤال، 'هل قيمة المسند صحيحة؟'".
• 1952  ( 1952 ) : يتضمن كلين مناقشة حول عدم إمكانية حل مشكلة التوقف لآلات تورينج ويعيد صياغتها من حيث الآلات التي "تتوقف في النهاية"، أي تتوقف: "...لا توجد خوارزمية لتحديد ما إذا كانت أي آلة معينة، عند بدء تشغيلها من أي وضع معين، ستتوقف في النهاية ." ^{[ 24 ]}
• 1952  ( 1952 ) : استخدم مارتن ديفيس مصطلح "مشكلة التوقف" في سلسلة من المحاضرات في مختبر أنظمة التحكم بجامعة إلينوي عام 1952. ومن المرجح أن يكون هذا هو أول استخدام لهذا المصطلح. ^{[ 26 ]}

تُشير العديد من الأبحاث والكتب الدراسية إلى بحث تورينج عام 1936 لتعريف وإثبات عدم قابلية حل مشكلة التوقف. إلا أن هذا غير صحيح. ^{[ 23 ] [ 27 ]} لم يستخدم تورينج مصطلحي "التوقف" أو "التوقف" في أي من أعماله المنشورة، بما في ذلك بحثه عام 1936. ^{[ 28 ]} أظهر بحث في الأدبيات الأكاديمية من عام 1936 إلى عام 1958 أن أول مادة منشورة استخدمت مصطلح "مشكلة التوقف" كانت لروجر (1957) . مع ذلك، يذكر روجرز أنه كان لديه مسودة لديفيس (1958) متاحة له، ^{[ 23 ]} ويذكر مارتن ديفيس في المقدمة أن "الخبير قد يجد بعض الجدة في ترتيب ومعالجة المواضيع"، ^{[ 29 ]} لذا يجب أن تُنسب هذه المصطلحات إلى ديفيس. ^{[ 23 ] [ 27 ]} ذكر ديفيس في رسالة أنه كان يشير إلى مشكلة التوقف منذ عام 1952. ^{[ 26 ]} الاستخدام في كتاب ديفيس هو كما يلي: ^{[ 30 ]}

«[...] نرغب في تحديد ما إذا كانت آلة تورينج Z، إذا وُضعت في حالة ابتدائية معينة، ستتوقف في النهاية أم لا. نسمي هذه المسألة مسألة توقف Z. [...]

النظرية 2.2 : توجد آلة تورينج التي تكون مشكلة توقفها غير قابلة للحل بشكل متكرر .

تتمثل المشكلة ذات الصلة في مشكلة الطباعة لآلة تورينج بسيطة Z فيما يتعلق بالرمز S _i ".

من المحتمل أن يكون بيان كلين لعام 1952 بمثابة مقدمة لصياغة ديفيس، والذي يختلف فقط في الصياغة: ^{[ 23 ] [ 24 ]}

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

تُعدّ مشكلة التوقف مكافئة تورينج لكلٍّ من مشكلة الطباعة لديفيس ("هل تطبع آلة تورينج، عند بدء تشغيلها من حالة معينة، رمزًا معينًا؟") ومشكلة الطباعة التي تناولها تورينج في بحثه عام 1936 ("هل تطبع آلة تورينج، عند بدء تشغيلها من شريط فارغ، رمزًا معينًا؟"). مع ذلك، فإنّ تكافؤ تورينج ليس دقيقًا تمامًا، ولا يعني أن المشكلتين متطابقتان. فهناك آلات تطبع دون أن تتوقف، وأخرى تتوقف دون أن تطبع. تتناول مشكلتا الطباعة والتوقف قضايا مختلفة، وتُظهران اختلافات مفاهيمية وتقنية جوهرية. لذا، كان ديفيس متواضعًا حين قال: ^{[ 23 ]}

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

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

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

توجد العديد من المسائل غير القابلة للحل؛ وأي مجموعة يكون فيها درجة تورينج مساوية لدرجة تورينج مسألة التوقف تُعدّ صياغةً من هذا القبيل. ومن أمثلة هذه المجموعات، بالإضافة إلى مسألة التوقف:

• { i | يتوقف البرنامج i في النهاية عند تشغيله بالمدخل 0}
• { i | يوجد مُدخل x بحيث يتوقف البرنامج i في النهاية عند تشغيله بالمدخل x }.

قدّم كريستوفر ستراشي برهانًا بالتناقض يُثبت أن مشكلة التوقف غير قابلة للحل. ^{[ 32 ] [ 33 ]} ويتم البرهان على النحو التالي: لنفترض وجود دالة قابلة للحساب كليًا halts(f) تُرجع القيمة true إذا توقف البرنامج الفرعي f (عند تشغيله بدون مدخلات) وتُرجع القيمة false خلاف ذلك. والآن، لننظر إلى البرنامج الفرعي التالي:

def g () -> None : if halts ( g ): loop_forever ()

يجب أن تُرجع الدالة `halts(g)` إما القيمة `true` أو `false`، لأن `halts` كانت تُفترض دالة حسابية كلية . إذا أرجعت `halts(g)` القيمة `true`، فستستدعي الدالة `loop_forever` ولن تتوقف أبدًا، وهذا تناقض. أما إذا أرجعت `halts(g) ` القيمة `false`، فستتوقف الدالة `g` ، لأنها لن تستدعي `loop_forever` ؛ وهذا أيضًا تناقض. إجمالًا، تقوم الدالة `g` بعكس ما تنص عليه ` halts` ، لذا لا يمكن لـ `halts(g)` أن تُرجع قيمة منطقية تتوافق مع ما إذا كانت `g` ستتوقف أم لا. لذلك، يجب أن يكون الافتراض الأولي بأن `halts` دالة حسابية كلية خاطئًا.

يوضح المفهوم أعلاه الطريقة العامة للبرهان، لكن الدالة القابلة للحساب التي تتوقف لا تأخذ روتينًا فرعيًا كمعامل بشكل مباشر؛ بل تأخذ شفرة المصدر لبرنامج. علاوة على ذلك، فإن تعريف g مرجعي ذاتيًا . ويتناول برهان دقيق هذه المشكلات. والهدف العام هو إثبات أنه لا توجد دالة قابلة للحساب كليًا تُحدد ما إذا كان برنامج i سيتوقف عند إدخال x عشوائي ؛ أي أن الدالة h التالية (اختصارًا لـ "يتوقف") غير قابلة للحساب: ^{[ 34 ]}

${\displaystyle h(i,x)={\begin{cases}1&{\text{if }}{\text{ program }}i{\text{ halts on input }}x,\\0&{\text{otherwise.}}\end{cases}}}$

هنا يشير البرنامج i إلى البرنامج رقم i في تعداد جميع البرامج الخاصة بنموذج حسابي ثابت كامل تورينج .

يتم البرهان من خلال إثبات أنه لا يمكن لأي دالة قابلة للحساب كليًا ذات وسيطين أن تكون الدالة المطلوبة h . وكما هو موضح في شرح المفهوم، فإنه بمعلومية أي دالة ثنائية قابلة للحساب كليًا f ، فإن الدالة الجزئية g التالية قابلة للحساب أيضًا بواسطة برنامج ما e :

${\displaystyle g(i)={\begin{cases}0&{\text{إذا كان }}f(i,i)=0,\\{\text{غير معرف}}&{\text{فيما عدا ذلك.}}\end{cases}}}$

يعتمد التحقق من أن الدالة g قابلة للحساب على البنى التالية (أو ما يعادلها):

• البرامج الفرعية القابلة للحساب (البرنامج الذي يحسب f هو برنامج فرعي في البرنامج e )،
• تكرار القيم (يحسب البرنامج e المدخلات i و i للدالة f من المدخل i للدالة g )،
• التفرع الشرطي (يختار البرنامج e بين نتيجتين بناءً على القيمة التي يحسبها لـ f ( i , i )),
• عدم إنتاج نتيجة محددة (على سبيل المثال، عن طريق التكرار إلى ما لا نهاية)،
• إرجاع قيمة 0.

يوضح الكود الزائف التالي لـ e طريقة مباشرة لحساب g :

الإجراء e ( i ) : إذا كانت f ( i , i ) تساوي 0 ، فأرجع 0، وإلا فاستمر في التكرار إلى ما لا نهاية.

بما أن الدالة g قابلة للحساب الجزئي، فلا بد من وجود برنامج e يحسب g ، بافتراض أن نموذج الحساب كامل تورينج. هذا البرنامج هو أحد البرامج التي تُعرَّف عليها دالة التوقف h . تُظهر الخطوة التالية من البرهان أن h ( e , e ) لن تكون لها نفس قيمة f ( e , e ).

يستنتج من تعريف g أنه يجب أن تتحقق إحدى الحالتين التاليتين فقط:

• f ( e , e ) = 0 وبالتالي g ( e ) = 0. في هذه الحالة يتوقف البرنامج e عند الإدخال e ، لذا h ( e , e ) = 1.
• بما أن f ( e , e ) ≠ 0، فإن g ( e ) غير مُعرَّفة. في هذه الحالة، لا يتوقف البرنامج e عند المدخل e ، لذا فإن h ( e , e ) = 0.

في كلتا الحالتين، لا يمكن أن تكون f هي نفس الدالة h . ولأن f كانت دالة قابلة للحساب الكلي بشكل عشوائي ذات وسيطين، فإن جميع هذه الدوال يجب أن تختلف عن h .

هذا البرهان مشابه لحجة كانتور القطرية . يمكن تصور مصفوفة ثنائية الأبعاد بعمود وصف لكل عدد طبيعي، كما هو موضح في الجدول أعلاه. تُوضع قيمة f ( i , j ) في العمود i والصف j . بما أن f دالة قابلة للحساب كليًا، يمكن حساب أي عنصر من عناصر المصفوفة باستخدام f . يمكن تصور بناء الدالة g باستخدام القطر الرئيسي لهذه المصفوفة. إذا كانت المصفوفة تحتوي على 0 في الموضع ( i , i )، فإن g ( i ) تساوي 0. وإلا، فإن g ( i ) غير مُعرّفة. ينشأ التناقض من وجود عمود e في المصفوفة يُقابل g نفسها. الآن، لنفترض أن f هي دالة التوقف h . إذا كانت الدالة g ( e ) مُعرَّفة (أي g ( e ) = 0 في هذه الحالة)، فإن البرنامج e يتوقف عند المدخل e ، وبالتالي f ( e,e ) = 1. لكن g ( e ) = 0 فقط عندما f ( e,e ) = 0، وهذا يُناقض f ( e,e ) = 1. وبالمثل، إذا كانت g ( e ) غير مُعرَّفة، فإن البرنامج e لا يتوقف عند المدخل e ، وبالتالي f ( e,e ) = 0، مما يؤدي إلى g ( e ) = 0 وفقًا لتعريف g . وهذا يُناقض فرضية عدم تعريف g ( e ). في كلتا الحالتين، ينشأ تناقض. لذلك، لا يُمكن لأي دالة قابلة للحساب f أن تكون دالة التوقف h .

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

تم التوصل إلى بعض النتائج المتعلقة بالأداء النظري لأساليب الاستدلال لحل مشكلة التوقف، ولا سيما نسبة البرامج ذات الحجم المحدد التي يمكن تصنيفها بشكل صحيح بواسطة خوارزمية تكرارية. لا تُعطي هذه النتائج أرقامًا دقيقة لأن النسب غير قابلة للحساب، كما أنها تعتمد بشكل كبير على اختيار ترميز البرنامج المستخدم لتحديد "الحجم". على سبيل المثال، لنفترض تصنيف البرامج حسب عدد حالاتها، واستخدام نموذج حسابي محدد "شريط تورينج شبه اللانهائي" الذي يُحدث خطأً (دون توقف) إذا تجاوز البرنامج الجانب الأيسر من الشريط.${\displaystyle \lim _{n\to \infty }P(x\,{\text{halts is decidable}}\mid x\,{\text{has}}\,n\,{\text{states}})=1}$، عبر البرامج${\displaystyle x}$يتم اختيارها بشكل موحد حسب عدد الحالات. لكن هذه النتيجة تبدو "بسيطة" إلى حد ما، لأن هذه البرامج القابلة للتقرير هي ببساطة تلك التي تُحذف من الشريط، والأسلوب الاستدلالي هو ببساطة التنبؤ بعدم التوقف بسبب الخطأ. وبالتالي، فإن تفصيلاً يبدو غير ذي صلة، ألا وهو معالجة البرامج التي تحتوي على أخطاء، قد يكون العامل الحاسم في تحديد نسبة البرامج. ^{[ 36 ]}

لتجنب هذه المشكلات، تم تطوير العديد من المفاهيم المقيدة لـ "حجم" البرنامج. يُعيّن ترقيم غودل الكثيف أرقامًا للبرامج بحيث تظهر كل دالة قابلة للحساب بنسبة موجبة في كل تسلسل من المؤشرات من 1 إلى n، أي أن ترقيم غودل φ يكون كثيفًا إذا وفقط إذا كان لكل${\displaystyle i}$يوجد${\displaystyle c>0}$بحيث${\displaystyle \liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c}$على سبيل المثال، نظام ترقيم يُعيّن فهارس.${\displaystyle 2^{n}}$بالنسبة للبرامج غير التافهة وجميع المؤشرات الأخرى، فإن حالة الخطأ ليست كثيفة، ولكن يوجد ترقيم غودل كثيف لبرامج Brainfuck الصحيحة نحويًا . ^{[ 37 ]} يُطلق على ترقيم غودل الكثيف اسم الترقيم الأمثل إذا كان، لأي ترقيم غودل آخر${\displaystyle \alpha }$، هناك دالة تكرارية كلية أحادية${\displaystyle f}$وثابت${\displaystyle c}$بحيث يكون ذلك لجميع${\displaystyle i}$،${\displaystyle \alpha _{i}=\phi _{f(i)}}$و${\displaystyle f(i)\leq ci}$يضمن هذا الشرط ألا تتجاوز فهارس جميع البرامج فهارسها في أي ترقيم غودل آخر. تُبنى ترقيمات غودل المثلى بترقيم مدخلات آلة تورينغ شاملة . ^{[ 38 ]} يستخدم مفهوم ثالث للحجم آلات شاملة تعمل على سلاسل ثنائية، ويقيس طول السلسلة اللازمة لوصف برنامج الإدخال. الآلة الشاملة U هي آلة يوجد لكل آلة أخرى V دالة قابلة للحساب الكلي h بحيث${\displaystyle V(x)=U(h(x))}$الآلة المثلى هي آلة شاملة تحقق حد ثبات تعقيد كولموغوروف ، أي أنه لكل آلة V ، يوجد عدد صحيح c بحيث أنه لكل مخرجات x ، إذا كان برنامج V بطول n يُخرج x ، فإنه يوجد برنامج U بطول لا يتجاوز${\displaystyle n+c}$إخراج x . ^{[ 39 ]}

نحن ندرس الدوال القابلة للحساب الجزئي (الخوارزميات).${\displaystyle A}$لكل${\displaystyle n}$نحن نعتبر الكسر${\displaystyle \epsilon _{n}(A)}$نسبة الأخطاء بين جميع البرامج ذات الحجم القياسي على الأكثر${\displaystyle n}$، مع احتساب كل برنامج${\displaystyle x}$والتي${\displaystyle A}$يفشل في الإنهاء، أو يُنتج إجابة "لا أعرف"، أو يُنتج إجابة خاطئة، أي${\displaystyle x}$توقفات و${\displaystyle A(x)}$المخرجات DOES_NOT_HALT، أو${\displaystyle x}$لا يتوقف و${\displaystyle A(x)}$المخرجات HALTS. يمكن وصف السلوك على النحو التالي، بالنسبة لعمليات غودل الكثيفة والآلات المثلى: ^{[ 37 ] [ 39 ]}

• لكل خوارزمية${\displaystyle A}$،${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$بعبارة أخرى، أي خوارزمية لها معدل خطأ أدنى إيجابي، حتى عندما يصبح حجم المشكلة كبيرًا للغاية.
• يوجد${\displaystyle \epsilon >0}$بحيث يكون لكل خوارزمية${\displaystyle A}$،${\displaystyle \limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon }$بعبارة أخرى، هناك معدل خطأ إيجابي ستؤدي أي خوارزمية إلى أداء أسوأ من معدل الخطأ هذا في كثير من الأحيان، حتى مع نمو حجم المشكلة إلى أجل غير مسمى.
• ${\displaystyle \inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0}$بمعنى آخر، توجد سلسلة من الخوارزميات بحيث يقترب معدل الخطأ من الصفر بشكل تعسفي لسلسلة محددة ذات أحجام متزايدة. مع ذلك، تسمح هذه النتيجة بوجود سلاسل من الخوارزميات تُنتج إجابات خاطئة.
• إذا اقتصرنا على النظر في الخوارزميات "الصادقة" التي قد تكون غير محددة ولكنها لا تنتج إجابات خاطئة أبدًا، فعندئذٍ، اعتمادًا على المقياس،${\displaystyle \inf _{A\,{\textrm {honest}}}\liminf _{n\to \infty }\epsilon _{n}(A)}$قد تكون قيمتها صفرًا أو لا. على وجه الخصوص، تكون قيمتها صفرًا بالنسبة للآلات الشاملة ذات المجموع الأيسر، ولكنها أكبر من صفر بالنسبة للآلات المثلى فعليًا. ^{[ 39 ]}

يعود تعقيد هذه الحدود إلى السلوك التذبذبي لـ${\displaystyle \epsilon _{n}(A)}$توجد أنواع جديدة من البرامج، وإن كانت نادرة الحدوث، تأتي في "كتل" كبيرة بشكل تعسفي، مع نسبة متزايدة باستمرار من البرامج المكررة. إذا تم تضمين كتل الأنواع الجديدة بالكامل، فإن معدل الخطأ يكون على الأقل${\displaystyle \epsilon }$لكن بين المجموعات، قد تكون نسبة التكرارات المصنفة بشكل صحيح عالية جدًا. وعلى وجه الخصوص، تسمح طريقة "العد" التي تتذكر ببساطة أول N مدخلات وتتعرف على مكافئاتها بالوصول إلى معدل خطأ منخفض جدًا بشكل متكرر. ^{[ 37 ]}

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

يمكن إثبات الصيغة الأضعف للنظرية من عدم قابلية حسم مسألة التوقف كما يلي. ^{[ 40 ]} لنفترض أن لدينا مجموعة بديهيات فعالة سليمة (وبالتالي متسقة) وكاملة لجميع عبارات منطق الرتبة الأولى الصحيحة حول الأعداد الطبيعية . عندئذٍ، يمكننا بناء خوارزمية تُحصي جميع هذه العبارات. هذا يعني وجود خوارزمية N ( n ) التي، عند إعطائها عددًا طبيعيًا n ، تحسب عبارة منطقية صحيحة من الرتبة الأولى حول الأعداد الطبيعية، وأنه لكل عبارة صحيحة، يوجد على الأقل عدد طبيعي واحد n بحيث تُنتج N ( n ) تلك العبارة. الآن، لنفترض أننا نريد تحديد ما إذا كانت الخوارزمية ذات التمثيل a تتوقف عند المدخل i . نعلم أنه يمكن التعبير عن هذه العبارة بعبارة منطقية من الرتبة الأولى، ولتكن H ( a , i ). بما أن مجموعة البديهيات كاملة، فإنه يترتب على ذلك إما وجود عدد طبيعي n بحيث N ( n ) = H ( a , i ) أو وجود عدد طبيعي n ′ بحيث N ( n ′ ) = ¬H ( a , i ). لذا، إذا كررنا العملية على جميع قيم n حتى نجد إما H ( a , i ) أو نفيها، فسنتوقف دائمًا، وعلاوة على ذلك، ستكون الإجابة التي نحصل عليها صحيحة (بحكم سلامة المنطق). هذا يعني أن لدينا خوارزمية لحل مشكلة التوقف. وبما أننا نعلم أنه لا يمكن وجود مثل هذه الخوارزمية، فإن افتراض وجود بديهية سليمة وكاملة وفعالة لجميع عبارات منطق الرتبة الأولى الصحيحة حول الأعداد الطبيعية هو افتراض خاطئ.

مشكلة التوقف الشامل ، والمعروفة أيضًا (في نظرية الاستدعاء الذاتي ) باسم "الشمولية" ، هي مشكلة تحديد ما إذا كان برنامج حاسوبي معين سيتوقف عند كل مُدخل (يأتي اسم "الشمولية" من السؤال المكافئ حول ما إذا كانت الدالة المحسوبة شاملة ). هذه المشكلة ليست غير قابلة للحل فحسب، كما هو الحال في مشكلة التوقف، بل هي غير قابلة للحل بدرجة كبيرة. من حيث التسلسل الهرمي الحسابي ، فهي${\displaystyle \Pi _{2}^{0}}$-مكتمل. ^{[ 42 ]}

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

توجد العديد من البرامج التي تُعيد، لبعض المدخلات، إجابة صحيحة لمشكلة التوقف، بينما لا تُعيد أي إجابة لمدخلات أخرى. مع ذلك، فإن مشكلة "بالنظر إلى البرنامج p ، هل هو حلّ جزئي لمشكلة التوقف؟" (بالمعنى الموصوف) لا تقل صعوبة عن مشكلة التوقف نفسها. ولتوضيح ذلك، لنفترض وجود خوارزمية PHSR ("مُعرِّف حلّ التوقف الجزئي") لحل هذه المشكلة. يمكن استخدامها لحل مشكلة التوقف، كما يلي: لاختبار ما إذا كان البرنامج x يتوقف عند المدخل y ، أنشئ برنامجًا p يُعيد القيمة "صحيح" عند المدخل ( x , y ) ويختلف عند جميع المدخلات الأخرى. ثم اختبر البرنامج p باستخدام PHSR.

إن الحجة السابقة هي اختزال لمشكلة التوقف إلى التعرف على نظام PHS، وبنفس الطريقة، يمكن اختزال المشكلات الأكثر صعوبة مثل التوقف عند جميع المدخلات ، مما يعني أن التعرف على نظام PHS ليس غير قابل للتقرير فحسب، بل هو أعلى في التسلسل الهرمي الحسابي ، على وجه التحديد${\displaystyle \Pi _{2}^{0}}$-مكتمل.

آلة تورينغ المفقودة هي آلة تورينغ قد يختفي فيها جزء من الشريط بشكل غير حتمي. مشكلة التوقف قابلة للحل بالنسبة لآلة تورينغ المفقودة، ولكنها ليست بدائية تكرارية . ^{[ 43 ]}

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