الترقيم (نظرية الحوسبة)

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

تشمل الأمثلة الشائعة للترقيم ترقيم غودل في منطق الرتبة الأولى ، وأرقام الوصف التي تنشأ من آلات تورينغ العالمية، والترقيم المقبول لمجموعة الدوال الجزئية القابلة للحساب.

ترقيم مجموعة​${\displaystyle S}$هي دالة جزئية شاملة من${\displaystyle \mathbb {N} }$إلى S ( إرشوف 1999: 477). قيمة الترقيم${\displaystyle \nu }$عند العدد i (إذا تم تعريفه) غالبًا ما يُكتب${\displaystyle \nu _{i}}$بدلاً من المعتاد${\displaystyle \nu (i)}$.

تتضمن أمثلة الترقيم ما يلي:

• مجموعة جميع المجموعات الجزئية المنتهية من${\displaystyle \mathbb {N} }$يحتوي على ترقيم${\displaystyle \gamma }$، محددة بحيث${\displaystyle \gamma (0)=\emptyset }$وبالتالي، لكل مجموعة غير فارغة منتهية${\displaystyle A=\{a_{0},\ldots ,a_{k}\}}$،${\displaystyle \gamma (n_{A})=A}$أين${\displaystyle n_{A}=\sum _{i\leq k}2^{a_{i}}}$(إرشوف 1999:477). هذا الترقيم هو إضافة.
• ترقيم غودل ثابت${\displaystyle \varphi _{i}}$يمكن استخدام الدوال الجزئية القابلة للحساب لتعريف ترقيم W للمجموعات القابلة للحساب ، وذلك بجعل W ( i ) مجالًا لـ${\displaystyle \varphi _{i}}$سيكون هذا الترقيم شاملاً (مثل جميع الترقيمات) ولكنه ليس أحاديًا: ستكون هناك أرقام مميزة تُطابق نفس المجموعة القابلة للحساب تحت W.

يكون الترقيم كليًا إذا كان دالة كلية. إذا كان مجال الترقيم الجزئي قابلًا للحساب والتعداد، فإنه يوجد دائمًا ترقيم كلي مكافئ (يُعرَّف تكافؤ الترقيم أدناه).

يكون الترقيم η قابلاً للتحديد إذا كانت المجموعة${\displaystyle \{(x,y):\eta (x)=\eta (y)\}}$هي مجموعة قابلة للتقرير.

يكون الترقيم η أحادي القيمة إذا كان η ( x ) = η ( y ) إذا وفقط إذا كان x = y ؛ أي إذا كانت η دالة أحادية. يُسمى الترقيم أحادي القيمة لمجموعة الدوال الجزئية القابلة للحساب بترقيم فريدبيرغ .

يوجد ترتيب مسبق على مجموعة جميع الترقيمات. ليكن${\displaystyle \nu _{1}:\mathbb {N} \rightharpoonup S}$و${\displaystyle \nu _{2}:\mathbb {N} \rightharpoonup S}$ليكن هناك ترقيمان. ثم${\displaystyle \nu _{1}}$يمكن اختزاله إلى${\displaystyle \nu _{2}}$مكتوب${\displaystyle \nu _{1}\leq \nu _{2}}$، لو

${\displaystyle \exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i).}$

أين${\displaystyle \mathbf {P} ^{(1)}}$هي مجموعة جميع الدوال القابلة للحساب الجزئي${\displaystyle \mathbb {N} \to \mathbb {N} }$.

لو${\displaystyle \nu _{1}\leq \nu _{2}}$و${\displaystyle \nu _{1}\geq \nu _{2}}$ثم ${\displaystyle \nu _{1}}$يعادل​​${\displaystyle \nu _{2}}$هذا مكتوب${\displaystyle \nu _{1}\equiv \nu _{2}}$.

عندما تكون عناصر المجموعة S المراد ترقيمها "بنائية" بما يكفي، فمن الشائع النظر إلى الترقيمات التي يمكن فك شفرتها بفعالية (إرشوف 1999: 486). على سبيل المثال، إذا كانت S تتكون من مجموعات قابلة للحساب، فإن الترقيم η يكون قابلاً للحساب إذا كانت مجموعة الأزواج ( x , y ) حيث y ∈ η ( x ) قابلة للحساب. وبالمثل، يكون ترقيم g للدوال الجزئية قابلاً للحساب إذا كانت العلاقة R ( x , y , z ) = "[ g ( x )]( y ) = z " قابلة للحساب (إرشوف 1999: 487).

يُطلق على الترقيم القابل للحساب اسم الترقيم الرئيسي إذا كان كل ترقيم قابل للحساب لنفس المجموعة قابلاً للاختزال إليه. وتشمل هذه المجموعة جميع المجموعات الفرعية القابلة للحساب من${\displaystyle \mathbb {N} }$ومجموعة جميع الدوال القابلة للحساب الجزئي لها ترقيم رئيسي (إرشوف 1999: 487). يُعرف الترقيم الرئيسي لمجموعة الدوال القابلة للحساب الجزئي في الأدبيات باسم الترقيم المقبول .

• ترقيم كامل
• التأسطوانة
• ترقيم غودل
• رقم الوصف

• YL Ershov (1999), "نظرية الترقيم"، كتيب نظرية الحوسبة ، Elsevier، ص  473 – 506.
• VA Uspenskiĭ , AL Semenov (1993), Algorithms: Main Ideas and Applications , Springer.