فك شفرة مجموعة مرقمة بشكل تراجعي

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



كان هناك خوارزمية ما بحيث تكون مجموعة الأرقام المدْخَلة فيها والتي تنتهي وتتوقّف عندها هذه الخوارِزِمية هي نفسها مجموعة الأرقام الموجودة في S.

أو، بشكلٍ مساوٍ،



إذا كان هناك خوارِزِميّة تسرد وتحصي بشكلٍ دقيق عناصر المجموعة S. فإنّ هذا يعني أنّ نواتج هذه الخوارِزِميّة ما هي إلا قائمة بعناصر المجموعة S: s1، s2، s3.... وإذا لزِم الأمر، فإن هذه الخوارِزِميّة قد لا تتوقّف أبدًا.

فالحالة الأولى توضِّح لماذا يُسْتَخدَم مصطلح «قابلة للحسم جزئيًا» في بعض الأحيان؛ في حين أنّ الحالة الثانية تشير إلى سبب استخدام مصطلح «قابلة للإحصاء حسابيًا». وغالبًا ما تُسْتَخدَم الاختصارات r.e. (مرقّمة بشكلٍ عوديّ)، و c.e. (قابلة للإحصاء حسابيًا)، بدلاً من العبارة كاملة حتى في الوسائل المطبوعة.

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











E









{\displaystyle {\mathcal {E}}}



.