قفزة تورينج

في نظرية الحوسبة ، فإن قفزة تورينج أو عامل قفزة تورينج ، الذي سمي على اسم آلان تورينج ، هو عملية تقوم بتعيين مشكلة قرار أصعب بشكل متتابع X ′ لكل مشكلة قرار X مع خاصية أن X ′ غير قابلة للتقرير بواسطة آلة أوراكل مع أوراكل لـ X.

يُطلق على هذا العامل اسم عامل القفز لأنه يزيد من درجة تورينج للمسألة X. أي أن المسألة X ′ غير قابلة للاختزال إلى X باستخدام تورينج . تُثبت نظرية بوست وجود علاقة بين عامل قفز تورينج والتسلسل الهرمي الحسابي لمجموعات الأعداد الطبيعية. ^{[ 1 ]} بعبارة أخرى، عند إعطاء مسألة ما، يُعيد عامل قفز تورينج مجموعة آلات تورينج التي تتوقف عند الوصول إلى وسيط (أوراكل) يحل تلك المسألة.

يمكن اعتبار قفزة تورينج لـ X بمثابة أوراكل لمشكلة التوقف بالنسبة لآلات الأوراكل التي ^لديها أوراكل لـ X. [ ^{1 ]}

بصورة رسمية، إذا أُعطيت مجموعة X وترقيم غودل φ _i ^X للدوال القابلة للحساب على X ، فإن قفزة تورينغ X ′ للمجموعة X تُعرَّف على النحو التالي:

$${\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{معرّفة}}\}.}$$

يتم تعريف قفزة تورينج رقم n ، X ^{( n ) ، استقرائيًا بواسطة}

$${\displaystyle {\begin{aligned}X^{(0)}&=X,\\X^{(n+1)}&=X^{(n)}{'}.\end{aligned}}}$$

القفزة ω X ( ^ω) للمجموعة X هي الربط الفعال لتسلسل المجموعات X ( ^{n ) لـ} n ∈ ℕ :

$${\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ and }}k\in X^{(i)}\},}$$

حيث يرمز p _i إلى العدد الأولي رقم i .

يُستخدم الرمز 0 ′ أو ∅ ′ غالبًا للدلالة على قفزة تورينج للمجموعة الفارغة. ويُقرأ " قفزة الصفر" أو أحيانًا "الصفر الأولي" .

وبالمثل، فإن 0 ^{( n )} هي القفزة رقم n للمجموعة الفارغة. بالنسبة لقيم n المحدودة ، ترتبط هذه المجموعات ارتباطًا وثيقًا بالتسلسل الهرمي الحسابي ، ^{[ 2 ]} وترتبط بشكل خاص بنظرية بوست .

يمكن تكرار القفزة في أعداد ترتيبية متسامية : هناك عوامل قفز${\displaystyle j^{\delta }}$بالنسبة لمجموعات الأعداد الطبيعية عندما${\displaystyle \delta }$هو عدد ترتيبي له رمز في كلين${\displaystyle {\mathcal {O}}}$^{(بغض النظر عن الكود، فإن} القفزات الناتجة متطابقة وفقًا لنظرية سبيكتور)، _[ ^{2 ] وعلى} _{وجه الخصوص ،} فإن المجموعات 0 ^(α) _لـ α < ω1CK ، حيث ω1CK هو الترتيبي ^لتشرش -كلين ، ترتبط ارتباطًا وثيقًا بالتسلسل الهرمي الحسابي الفائق . ^{[ 1 ]} بعد ω1CK ^، يمكن مواصلة العملية عبر الترتيبيات القابلة للعد في الكون القابل للبناء ، باستخدام عمل جنسن حول نظرية البنية الدقيقة لـ L لغودل . ^{[ 3 ] [ 2 ]} وقد تم تعميم المفهوم أيضًا ليشمل الأعداد الأصلية المنتظمة غير القابلة للعد . ^{[ 4 ]}

• إن قفزة تورينج 0 ′ للمجموعة الفارغة مكافئة تورينج لمسألة التوقف . ^{[ 5 ]}
• لكل n ، تكون المجموعة 0 ^{( n )} كاملة من النوع m عند المستوى${\displaystyle \Sigma _{n}^{0}}$في التسلسل الهرمي الحسابي (بحسب نظرية بوست ).
• يمكن حساب مجموعة أعداد غودل للصيغ الصحيحة في لغة حساب بيانو مع مسند لـ X من X ^(ω) . ^{[ 3 ]}

• X ′ قابلللتعداد الحسابي X ولكنهليس قابلاً للحساب X.
• إذا كانت A مكافئة تورينج لـ B ، فإن A ′ مكافئة تورينج لـ B ′ . عكس هذا الاستلزام غير صحيح.
• ( شور وسلامان ، 1999 ) يمكن تعريف الدالة التي تربط X بـ X ′ في الترتيب الجزئي لدرجات تورينج. ^{[ 5 ]}

تمت مناقشة العديد من خصائص عامل قفزة تورينج في المقالة المتعلقة بدرجات تورينج .

• أمبوس-سبيس، ك. وفيجر، ب. درجات عدم قابلية الحل. غير منشور. https://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• ليرمان، م. (1983). درجات عدم قابلية الحل: النظرية المحلية والعالمية . برلين؛ نيويورك: سبرينغر-فيرلاغ . ISBN 3-540-12155-2.
• لوبارسكي، روبرت س. (ديسمبر 1987). "الرموز الرئيسية غير القابلة للعد والتسلسل الهرمي للقفز". مجلة المنطق الرمزي . المجلد  52، العدد  4. الصفحات 952-958 . JSTOR 2273829 .  
• روغرز الابن، هـ. (1987). نظرية الدوال التكرارية والحسابية الفعالة . مطبعة معهد ماساتشوستس للتكنولوجيا ، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية. ISBN 0-07-053522-1.
• شور، ر. أ.؛ سلامان، ت. أ. (1999). "تعريف قفزة تورينج" (ملف PDF) . رسائل البحوث الرياضية . 6 ( 5-6 ): 711-722 . doi : 10.4310/mrl.1999.v6.n6.a10 . تاريخ الاسترجاع: 13 يوليو 2008 .
• سواري، آر آي (1987). المجموعات القابلة للتعداد التكراري والدرجات: دراسة للدوال القابلة للحساب والمجموعات المولدة حسابيًا . سبرينغر. ISBN 3-540-15299-7.