الترقيم المسموح به

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

تُظهر نظرية تكافؤ روجرز أن جميع أنظمة البرمجة المقبولة متكافئة مع بعضها البعض بالمعنى الرسمي لنظرية الترقيم.

أدى صياغة نظرية الحوسبة من قِبل كلين إلى دالة حسابية جزئية شاملة خاصة، Ψ( e , x )، مُعرَّفة باستخدام المسند T. هذه الدالة شاملة بمعنى أنها قابلة للحساب الجزئي ، ولكل دالة حسابية جزئية f، يوجد عدد حقيقي e بحيث يكون، لكل x ، f ( x ) = Ψ( e , x )، حيث تعني المساواة إما أن كلا الطرفين غير مُعرَّفين أو كلاهما مُعرَّفان ومتساويان. من الشائع كتابة ψe ₍ x ) بدلاً من Ψ( e , x )؛ وبالتالي فإن المتتالية ψ₀ _، ψ₁ _، ... هي تعداد لجميع الدوال الحسابية الجزئية. تُسمى هذه التعدادات رسميًا بالترقيم الحسابي للدوال الحسابية الجزئية.

يُعرَّف الترقيم التعسفي η للدوال الجزئية بأنه ترقيم مقبول إذا:

• الدالة H ( e , x ) = η _e ( x ) هي دالة قابلة للحساب جزئيًا.
• توجد دالة قابلة للحساب الكلي f بحيث يكون، لكل e ، η _e = ψ _{f ( e )} .
• توجد دالة قابلة للحساب الكلي g بحيث يكون، لجميع e ، ψ _e = η _{g ( e )} .

هنا، تتطلب النقطة الأولى أن يكون الترقيم قابلاً للحساب؛ وتتطلب النقطة الثانية أن يكون من الممكن تحويل أي فهرس للترقيم η بشكل فعال إلى فهرس للترقيم ψ؛ وتتطلب النقطة الثالثة أن يكون من الممكن تحويل أي فهرس للترقيم ψ بشكل فعال إلى فهرس للترقيم η .

يتميز التوصيف المكافئ التالي للمقبولية بكونه "داخليًا لـ η "، حيث لا يشير بشكل مباشر إلى ترقيم معياري (بل بشكل غير مباشر فقط من خلال تعريف شمولية تورينج). يكون ترقيم الدوال الجزئية η مقبولًا بالمعنى المذكور أعلاه إذا وفقط إذا :

• دالة التقييم H ( e , x ) = η _e ( x ) هي دالة قابلة للحساب جزئيًا.
• η هي خاصية تورينج العالمية: لكل الدوال الجزئية القابلة للحساب f يوجد e بحيث η _e = f (لاحظ أننا هنا لا نفترض دالة قابلة للحساب كليًا تحول مؤشرات η إلى مؤشرات ψ).
• η لها " الحساب الجزئي " أو تحقق نظرية المعلمة أو نظرية Smn ، أي أن هناك دالة قابلة للحساب الكلي c بحيث يكون لجميع e ، x ، y ، η _{c ( e ، x )} ( y )= η _e ( x ، y ).

والبرهان كالتالي:

إن حقيقة أن الترقيمات المقبولة بالمعنى المذكور أعلاه لها كل هذه الخصائص تتبع من حقيقة أن الترقيم القياسي له كل هذه الخصائص، ونظرية تكافؤ روجرز.

في الاتجاه الآخر، لنفترض أن η لها الخصائص الموجودة في التوصيف المكافئ.

بما أن دالة التقييم H ( e , x ) = ηe ( x ) قابلة للحساب جزئيًا، فإنه يوجد v بحيث ψv ₌ H. وبالتالي ، وفقًا لنظرية المعامل للترقيم القياسي، توجد دالة قابلة للحساب كليًا d _بحيث ψd _{( v , e )} ( x ) = H ( e , x ) لجميع قيم x . وبذلك ، تحقق الدالة الكلية f ( e ) = d ( v , _e ) الجزء الثاني من التعريف أعلاه.

بعد ذلك، بما أن دالة التقييم E ( e , x )=ψ _e ( x ) للترقيم القياسي قابلة للحساب جزئيًا، وبافتراض عالمية تورينج يوجد u بحيث η _u ( e , x )=ψ _e ( x ) لجميع e , x .

لتكن c ( x , e ) دالة التقريب القابلة للحساب لـ η . عندئذٍ ηc _{( u , e )} = ψe _لجميع e ، لذا فإن g ( e ) = c ( u , _e ) تحقق الجزء الثالث من التعريف الأول أعلاه.

أظهر هارتلي روجرز الابن أن ترقيم η للدوال الجزئية القابلة للحساب مقبول إذا وفقط إذا كان هناك تقابل كلي قابل للحساب p بحيث يكون، لجميع e ، η _e = ψ _{p ( e )} (Soare 1987:25).

• ترقيم فريدبيرغ

• YL Ershov ( 1999)، "نظرية الترقيم"، كتيب نظرية الحوسبة ، ER Griffor (محرر)، Elsevier، ص  473-506 . ISBN 978-0-444-89882-1
• م. ماختي وب. يونغ (1978)، مقدمة في النظرية العامة للخوارزميات ، نورث هولاند، 1978. ISBN 0-444-00226-X
• إتش. روجرز الابن (1967)، نظرية الدوال التكرارية والحوسبة الفعالة ، الطبعة الثانية 1987، مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 0-262-68052-1(غلاف ورقي)، رقم ISBN 0-07-053522-1
• آر. سواري (1987)، المجموعات والدرجات القابلة للتعداد بشكل متكرر ، وجهات نظر في المنطق الرياضي، سبرينغر-فيرلاغ. ISBN 3-540-15299-7