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

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

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

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

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

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

التعريف المنهجيّ

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

صِيَغ متكافِئة

فيما يلي جميع الخصائص المتكافئة لمجموعة الأعداد الطبيعية S:

قابلية الحسم جزئيًا:

• إنّ المجموعة S مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها)، وهذا يعني أنّ S هي مجال (أو مجال مساوٍ) لأي دالة جزئية متكرِّرة.
• فيما يلي مثال على دالة جزئية متكرِّرة (F):

$f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.$

قابلية العد:

• إنّ المجموعة S هي مجال لأي دالة جزئية متكرِّرة.
• إنّ المجموعة S هي مجال لأي دالة كلية متكرِّرة أو خالية. فإذا كانت S مجموعة مُطْلقة (أو لانهائية)، فإنّه يمكن اختيار الدالة في هذه الحالة لتصبح دالة متباينة.
• إنّ المجموعة S هي مجال لأي دالة بدائية متكرِّرة أو خالية. فحتى إذا كانت S مجموعة مُطْلقة (أو لانهائية)، فقد يكون من الضروريّ في هذه الحالة تكرار وإعادة القيِم العددية.

الديوفانتية:

• إذا كان هناك كثيرة حدود رمزها P، وكانت تحتوي على المعاملات الصحيحة والمتغيرات x, a, b, c, d, e, f, g, h, i في نطاق مجموعة الأعداد الطبيعية بهذه الطريقة:

$x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).$

• إذا كان هناك كثيرة حدود تبدأ بأعداد صحيحة وتنتهي بأعداد صحيحة بحيث تحوي المجموعة S في نطاقها وبشكلٍ دقيق على الأعداد غير السالبة.

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

أمثلة

• إن كل مجموعة متكررة هي مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها)، ولكن ليست كل مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها) هي في الأصل مجموعة متكرّرة.
• أي لغة يمكن إحصاء تكرارها هي مجموعة يمكن إحصاء تكرارها وتمثِّل جزءًا من أي لغة اصطلاحية.
• إنّ المجموعة المكوِّنة لجميع الجمل التي يمكن إثباتها بالبرهان وبنظام بدهيٍّ مُقدّم بشكلٍ فعّال هي مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها).
• تُفيد نظرية ماتياسيفيتش بأنّ كل مجموعة مرقّمة بشكلٍ عوديّ هي مجموعة ديوفانتية (والعكس يمكن إثبات صحته بسهولة).
• إنّ المجموعات البسيطة هي مجموعات مرقّمة بشكلٍ عوديّ ولكنها غير متكرِّرة.
• إنّ المجموعات المبتكَرة هي مجموعات مرقّمة بشكلٍ عوديّ ولكنها غير متكرِّرة.
• إن أي مجموعة ذات نواتج ليست مرقمةً بشكلٍ عوديّ.
• باستخدام ترقيم جودل $\phi$ في الدوال القابلة للحساب، تكون المجموعة $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ مرقمة بشكلٍ عوديّ (حيث أنّ $\langle i,x\rangle$ هي دالة كانتور الثنائية و$\phi _{i}(x)\downarrow$ تشير إلى أنّ$\phi _{i}(x)$ مُعرّف). وتقوم هذه المجموعة بترميز المشكلة الخاصة بإيقاف التشغيل حيث أنّها تصف العوامل المتغيرة المُدْخَلة والتي تتوقف عندها كل آلة تورنغ عن العمل.
• باستخدام ترقيم جودل $\phi$ في الدوال القابلة للحساب، تكون المجموعة $\lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace$ مرقمة بشكلٍ عوديّ. وتقوم هذه المجموعة بترميز مسألة حساب قيمة دالة.
• باستخدام الدالة الجزئية ƒ والتي تبدأ بالأعداد الطبيعية وتنتهي بالأعداد الطبيعية، تكون ƒ دالة جزئية متكررة فقط إذا كان الرسم البياني للدالة ƒ يعبر عن مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها) وتمثِّل تلك المجموعة جميع الأطراف الثنائية $\langle x,f(x)\rangle$ بالطريقة التي يكون فيها f(x) معرّفًا.

الخصائص

إذا كانت A و B مجموعتان مرقّمتان بشكلٍ عوديّ، فإنّ A ∩ B, A ∪ B and A × B هي مجموعات (يمكن إحصاء تكرارها) مرقّمة بشكلٍ عوديّ، (حيث يرتبط زوج الأعداد الطبيعية المرتب مع عدد طبيعي واحد ليشكِّلا دالة كانتور الثنائية). إنّ الصورة العكسية لأي مجموعة يمكن إحصاء تكرارها في ظل دالة جزئية متكرِّرة هي أيضًا مجموعة يمكن إحصاء تكرارها.

وتكون أي مجموعة مرقّمة بشكلٍ عوديّ فقط إذا كانت عند المستوى $\Sigma _{1}^{0}$ من الهرم الحسابي.

ويمكن القول بأنّ المجموعة T مرقمة بشكلٍ عودي ومكمِّل أو co-r.e. إذا كان المكمِّل لها $\mathbb {N} \setminus T$ مرقّم بشكلٍ عوديّ (أو يمكن إحصاء تكراره). وبالمثل تكون أي مجموعة مرقمة بشكلٍ عودي ومكمِّل فقط إذا كانت عند المستوى $\Pi _{1}^{0}$ من الهرم الحسابي.

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

ملاحظات

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

المراجع

• Rogers, H. The Theory of Recursive Functions and Effective Computability, ميت بريس. ISBN 0-262-68052-1; ISBN 0-07-053522-1.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. سبرنجر، Berlin, 1987. ISBN 3-540-15299-7.
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.