درجة تورينج

في علوم الحاسوب والمنطق الرياضي، تقيس درجة تورينج (المسماة على اسم آلان تورينج ) أو درجة عدم قابلية حل مجموعة من الأعداد الطبيعية مستوى عدم قابلية حل المجموعة خوارزميًا.

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

تكون مجموعتان متكافئتين تورينج إذا كانت لهما نفس درجة عدم قابلية الحل؛ كل درجة تورينج هي مجموعة من المجموعات المتكافئة تورينج، لذا فإن مجموعتين تكونان في درجتي تورينج مختلفتين تحديدًا عندما لا تكونان متكافئتين تورينج. علاوة على ذلك، فإن درجات تورينج مرتبة جزئيًا ، بحيث إذا كانت درجة تورينج لمجموعة X أقل من درجة تورينج لمجموعة Y ، فإنه يمكن تحويل أي إجراء (قد يكون غير قابل للحساب) يحدد بشكل صحيح ما إذا كانت الأعداد تنتمي إلى Y إلى إجراء يحدد بشكل صحيح ما إذا كانت الأعداد تنتمي إلى X. وبهذا المعنى، تتوافق درجة تورينج لمجموعة ما مع مستوى عدم قابليتها للحل الخوارزمي.

طُرحت درجات تورينج بواسطة بوست (1944) ، وأثبت كلين وبوست (1954) العديد من النتائج الأساسية . ومنذ ذلك الحين، أصبحت درجات تورينج مجالًا خصبًا للبحث المكثف. وتعتمد العديد من البراهين في هذا المجال على أسلوب إثبات يُعرف باسم أسلوب الأولوية .

فيما تبقى من هذه المقالة، سيشير مصطلح " مجموعة " إلى مجموعة الأعداد الطبيعية. يُقال إن المجموعة X قابلة للاختزال بواسطة آلة تورينج إلى المجموعة Y إذا وُجدت آلة تورينج قادرة على تحديد انتماء عنصر ما إلى X عند إعطائها آلة تورينج أخرى لتحديد انتمائه إلى Y. ويُشير الرمز X ≤ _TY إلى أن X قابلة للاختزال بواسطة آلة تورينج إلى Y.

يُعرَّف أن مجموعتين X و Y متكافئتان تورينجيًا إذا كانت X قابلة للاختزال تورينجيًا إلى Y و Y قابلة للاختزال تورينجيًا إلى X. يشير الرمز X ≡ _T Y إلى أن X و Y متكافئتان تورينجيًا. يمكن اعتبار العلاقة ≡ _T علاقة تكافؤ ، مما يعني أنه لجميع المجموعات X و Y و Z :

• X ≡ _T X
• X ≡ _TY يستلزم Y ≡ _TY X​
• إذا كان X ≡ _TY و Y ≡ _TZ فإن X ≡ _TZ .​​

درجة تورينج هي فئة تكافؤ للعلاقة ≡ _T. يرمز [ X ] إلى فئة التكافؤ التي تحتوي على المجموعة X. ويُرمز إلى المجموعة الكاملة لدرجات تورينج بـ${\displaystyle {\mathcal {D}}}$.

تُعرَّف درجات تورينج بترتيب جزئي ≤ بحيث يكون [ X ] ≤ [ Y ] إذا وفقط إذا كان X ≤ _TY . توجد درجة تورينج فريدة تحتوي على جميع المجموعات القابلة للحساب ، وهذه الدرجة أقل من أي درجة أخرى. يُرمز لها بـ 0 (صفر) لأنها أصغر عنصر في المجموعة المرتبة جزئيًا .${\displaystyle {\mathcal {D}}}$(من الشائع استخدام الترميز الغامق لدرجات تورينج، وذلك لتمييزها عن المجموعات. عندما لا يكون هناك احتمال للالتباس، كما هو الحال مع [ X ]، فإن استخدام الترميز الغامق ليس ضرورياً.)

لأي مجموعتين X و Y ، تُعرَّف المجموعة X ⊕ Y ، والتي تُكتب X ⊕ Y ، بأنها اتحاد المجموعتين { 2n  : n ∈ X } و { 2m + 1  : m ∈ Y } . درجة تورينج للمجموعة X ⊕ Y هي أصغر حد أعلى لدرجات المجموعتين X و Y.${\displaystyle {\mathcal {D}}}$هي شبكة شبه متصلة . يُرمز إلى الحد الأدنى الأعلى للدرجتين a و b بالرمز a ∪ b . من المعروف أن${\displaystyle {\mathcal {D}}}$ليست شبكة ، حيث توجد أزواج من الدرجات بدون حد أدنى أقصى.

لأي مجموعة X، يرمز X ′ إلى مجموعة مؤشرات آلات أوراكل التي تتوقف (عند إدخال مؤشرها) عند استخدام X كأوراكل. تُسمى المجموعة X ′ قفزة تورينج لـ X. تُعرَّف قفزة تورينج للدرجة [ X ] بأنها الدرجة [ X ′ ]؛ وهذا تعريف صحيح لأن X ′ ≡ _TY ′ عندما X ≡ _TY . مثال رئيسي على ذلك هو 0 ′ ، درجة مشكلة التوقف .

• كل درجة تورينج هي عدد لانهائي قابل للعد ، أي أنها تحتوي على عدد لا نهائي من الدرجات.${\displaystyle \aleph _{0}}$مجموعات.
• هناك${\displaystyle 2^{\aleph _{0}}}$درجات تورينج المتميزة.
• لكل درجة a، يتحقق التباين الصارم a < a ′ .
• لكل درجة a ، تكون مجموعة الدرجات الأقل من a قابلة للعد . أما مجموعة الدرجات الأكبر من a فلها حجم${\displaystyle 2^{\aleph _{0}}}$.

أُجريت أبحاثٌ كثيرةٌ حول بنية درجات تورينج. يُدرج الاستعراض التالي بعضًا من النتائج المعروفة. ومن الاستنتاجات العامة التي يمكن استخلاصها من هذه الأبحاث أن بنية درجات تورينج بالغة التعقيد.

تُسمى الدرجة قابلة للتعداد التكراري (re) أو قابلة للتعداد الحسابي (ce) إذا احتوت على مجموعة قابلة للتعداد التكراري . كل درجة re أقل من 0 ′ ، ولكن ليس كل درجة أقل من 0 ′ قابلة للتعداد التكراري. ومع ذلك، فإن المجموعة${\displaystyle A}$يكون النظام متعدد العناصر قابلاً للاختزال إلى 0 ′ إذا وفقط إذا${\displaystyle A}$هو إعادة. ^{[ 3 ]}

• ساكس (1964) : درجات re كثيفة؛ بين أي درجتين re توجد درجة re ثالثة.
• لاكلان (1966أ) و ييتس (1966) : هناك درجتان re بدون حد أدنى أكبر في درجات re.
• لاكلان (1966أ) و ييتس (1966) : هناك زوج من درجات re غير الصفرية التي يكون حدها الأدنى الأكبر هو 0 .
• لاكلان (1966ب) : لا يوجد زوج من درجات re يكون حده الأدنى الأكبر 0 وحده الأعلى الأصغر 0 ′ . تُعرف هذه النتيجة بشكل غير رسمي باسم نظرية اللا ماسية .
• توماسون (1971) : يمكن تضمين كل شبكة توزيعية منتهية في درجات re. في الواقع، يمكن تضمين الجبر البولياني القابل للعد وغير الذري بطريقة تحافظ على القيم العليا والدنيا .
• لاكلان وسوار (1980) : لا يمكن تضمين جميع الشبكات المحدودة في درجات re (عبر تضمين يحافظ على القيم العليا والدنيا). يُعرض مثال محدد على اليمين.
• LA Harrington و TA Slaman (انظر Nies و Shore و Slaman (1998) ): إن نظرية الدرجة الأولى للدرجات re في اللغة ⟨ 0 , ≤ , = ⟩ هي مكافئة متعددة-واحد لنظرية الحساب الحقيقي من الدرجة الأولى .

بالإضافة إلى ذلك، هناك نظرية شوينفيلد للحدود، حيث تحقق المجموعة A ما يلي:${\displaystyle [A]\leq _{T}\emptyset '}$إذا وفقط إذا كان هناك "تقريب تكراري" لدالتها المميزة: دالة g بحيث أنه بالنسبة لقيم s الكبيرة بما فيه الكفاية ،${\displaystyle g(s)=\chi _{A}(s)}$[ ^{4 ]​}

تُسمى المجموعة A مجموعة من الدوال من الرتبة n -r.${\displaystyle (A_{s})_{s\in \mathbb {N} }}$بحيث: ^{[ 4 ]}

• A _s هو تقريب تكراري لـ A : لأي قيمة t ، ولأي s ≥ t، لدينا A _s ( x ) = A ( x )، مع دمج A ودالتها المميزة . (إزالة هذا الشرط تعطي تعريفًا لـ A بأنها "تكرارية ضعيفة من الرتبة n " ).
• A _s هو " مسند من المحاولات n ": لكل x ، A ₀ ( x )=0 وعدد عناصر${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$هو ≤ ن .

خصائص الدرجات من الرتبة n : ^{[ 4 ]}

• تُعد فئة المجموعات ذات الدرجة n -re فئة فرعية صارمة من فئة المجموعات ذات الدرجة ( n +1)-re.
• لكل n > 1، توجد درجتان من الرتبة ( n + 1) re ، a و b ، بحيث${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$بحيث يكون الجزء${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$لا يحتوي على درجات n -re.
• ${\displaystyle A}$و${\displaystyle {\overline {A}}}$تكون المجموعات ( n + 1)-re إذا وفقط إذا كانت كلتا المجموعتين ضعيفة- n -re

درس إميل بوست  درجات تورينج re وتساءل عما إذا كانت هناك أي درجة re تقع تحديدًا بين 0 و 0 ′ . عُرفت مشكلة بناء مثل هذه الدرجة (أو إثبات عدم وجودها) باسم مشكلة بوست . حُلّت هذه المشكلة بشكل مستقل من قِبل فريدبيرج وموشنيك في خمسينيات القرن العشرين، حيث أثبتا وجود درجات re الوسيطة هذه ( نظرية فريدبيرج-موشنيك ). طوّر كلٌّ من برهانيهما نفس الطريقة الجديدة لبناء درجات re، والتي عُرفت فيما بعد بطريقة الأولوية . تُعدّ طريقة الأولوية الآن التقنية الرئيسية لإثبات النتائج المتعلقة بمجموعات re.

تعتمد فكرة طريقة الأولوية لإنشاء مجموعة إعادة X على سرد سلسلة قابلة للعد من المتطلبات التي يجب أن تستوفيها X. على سبيل المثال، لإنشاء مجموعة إعادة X بين 0 و 0 ′، يكفي استيفاء الشرطين A_{_e} و B_{_e} لكل عدد طبيعي e ، حيث يشترط A _{_e} ألا تحسب آلة أوراكل ذات الفهرس e القيمة 0 ′ من X ، ويشترط B _{_e} ألا تحسب آلة تورينج ذات الفهرس e (بدون أوراكل) القيمة X. تُوضع هذه المتطلبات في ترتيب أولوية ، وهو عبارة عن تقابل صريح بين المتطلبات والأعداد الطبيعية. يسير البرهان استقرائيًا بمرحلة واحدة لكل عدد طبيعي؛ ويمكن اعتبار هذه المراحل خطوات زمنية يتم خلالها تعداد المجموعة X. في كل مرحلة، يمكن إضافة أعداد إلى X أو منعها نهائيًا (إن لم تتضرر) من دخول X في محاولة لاستيفاء المتطلبات (أي، فرض تحققها بمجرد تعداد جميع عناصر X ). أحيانًا، يمكن إدراج عدد في المجموعة X لتلبية أحد المتطلبات، لكن هذا قد يؤدي إلى عدم تلبية متطلب مُلبّى سابقًا (أي تضرره ) . يُستخدم ترتيب الأولوية للمتطلبات لتحديد المتطلب الذي يجب تلبيته في هذه الحالة. الفكرة العامة هي أنه إذا تضرر متطلب ما، فسيتوقف تضرره في النهاية بعد توقف تضرر جميع المتطلبات ذات الأولوية الأعلى، مع العلم أن هذه الخاصية لا تنطبق على جميع حجج الأولوية. يجب تقديم حجة تثبت أن المجموعة X كاملة (re) وتلبي جميع المتطلبات. يمكن استخدام حجج الأولوية لإثبات العديد من الحقائق حول المجموعات (re)؛ ويجب اختيار المتطلبات المستخدمة وطريقة تلبيتها بعناية للوصول إلى النتيجة المطلوبة.

على سبيل المثال، يمكن إنشاء X منخفض بسيط (وبالتالي غير قابل للحساب) (حيث يعني منخفض أن _X ′ = 0′) _في عدد لا نهائي من المراحل كما يلي. في بداية المرحلة n ، ليكن Tn هو شريط الإخراج ( الثنائي)، والذي يُعرَّف بمجموعة مؤشرات الخلايا التي وضعنا فيها 1 حتى الآن (أي X = ∪ _n Tn ؛ T0 = _∅ ) ؛ وليكن Pn ₍ m ) هو أولوية عدم إخراج 1 في الموقع m ؛ P0 ₍ m ) = ∞ . في المرحلة n ، إن أمكن (وإلا فلا تفعل شيئًا في هذه المرحلة)، اختر أصغر i < n بحيث يكون ∀m Pn ( m ) ≠ i وتتوقف آلة تورينج i في أقل من n خطوة _عند مدخل S ⊇ Tn بحيث _يكون ∀m ∈ S \ Tn _{Pn (} m ) ≥ i . اختر أي مجموعة بيانات S (محدودة) ، واجعل T _{_{n +1}} = S ، ولكل خلية m زارتها الآلة i في S ، اجعل P _{_{n +1}} ( m ) = min( i , P _{_n} ( m ))، واجعل جميع الأولويات الأكبر من i تساوي ∞، ثم اجعل خلية واحدة ذات أولوية ∞ (أي خلية تفي بالغرض) ليست ضمن S ذات أولوية i . باختصار، نجعل الآلة i تتوقف إذا أمكننا فعل ذلك دون التأثير على الأولويات الأصغر من i ، ثم نضبط الأولويات لمنع الآلات الأكبر من i من تعطيل التوقف؛ جميع الأولويات ثابتة في النهاية.

لإثبات أن X منخفضة، تتوقف الآلة i عند X إذا وفقط إذا توقفت في أقل من n خطوة على مجموعة T _n بحيث تتوقف الآلات < i التي تتوقف عند X في أقل من n − i خطوة (بالاستدلال، يمكن حساب ذلك بشكل منتظم من 0′). X غير قابلة للحساب لأنه بخلاف ذلك، يمكن لآلة تورينج أن تتوقف عند Y إذا وفقط إذا كانت Y \ X غير فارغة، مما يناقض البناء لأن X تستبعد بعض خلايا الأولوية i لأي قيمة كبيرة لـ i ؛ و X بسيطة لأن عدد خلايا الأولوية i محدود لكل i .

• مقياس مارتن