آلة تورينج المتناوبة

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 43 صور
الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعرَّف آلة تورينغ المتناوبة ( ATM ) بأنها آلة تورينغ غير حتمية ( NTM ) ذات قاعدة لقبول العمليات الحسابية تُعمِّم القواعد المستخدمة في تعريف فئتي التعقيد NP و co-NP . وقد طُرِح مفهوم آلة تورينغ المتناوبة من قِبَل تشاندرا وستوكمير [ 1 ] ، وبشكل مستقل من قِبَل كوزين [ 2 ] في عام 1976، ونُشِرَ بحثٌ مشتركٌ في مجلة علمية عام 1981. [ 3 ]

التعريفات

وصف غير رسمي

يعتمد تعريف NP على نمط الحساب الوجودي : إذا أدى أي خيار إلى حالة قبول، فإن الحساب بأكمله يقبل. أما تعريف co-NP فيعتمد على نمط الحساب الشامل : فقط إذا أدت جميع الخيارات إلى حالة قبول، فإن الحساب بأكمله يقبل. وتتناوب آلة تورينغ المتناوبة (أو بتعبير أدق، تعريف القبول لهذه الآلة) بين هذين النمطين.

آلة تورينغ المتناوبة هي آلة تورينغ غير حتمية، تُقسّم حالاتها إلى مجموعتين: حالات وجودية وحالات شاملة . تكون الحالة الوجودية مقبولة إذا أدى أي انتقال إلى حالة قبول؛ وتكون الحالة الشاملة مقبولة إذا أدى كل انتقال إلى حالة قبول. (وبالتالي، تقبل الحالة الشاملة التي لا تحتوي على انتقالات بشكل مطلق؛ وترفض الحالة الوجودية التي لا تحتوي على انتقالات بشكل مطلق). تقبل الآلة ككل إذا كانت حالتها الابتدائية مقبولة.

التعريف الرسمي

بصورة رسمية، فإن آلة تورينج المتناوبة (ذات الشريط الواحد) هي عبارة عن مجموعة من 5 عناصرم=(سؤال،Γ،دلتا،q0،ز){\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}أين

  • سؤال{\displaystyle Q}هي مجموعة محدودة من الحالات
  • Γ{\displaystyle \Gamma }الأبجدية الشريطية المحدودة
  • دلتا:سؤال×Γ→P(سؤال×Γ×{ل،R}){\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}تُسمى دالة الانتقال ( L تحرك الرأس إلى اليسار و R تحرك الرأس إلى اليمين)
  • q0∈سؤال{\displaystyle q_{0}\in Q}هي الحالة الأولية
  • ز:سؤال→{∧،∨،أججهـصت،رهـجهـجت}{\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}يحدد نوع كل ولاية

إذا كان M في حالةq∈سؤال{\displaystyle q\in Q}معز(q)=أججهـصت{\displaystyle g(q)=accept}عندئذٍ يُقال إن هذا التكوين يقبل ، وإذاز(q)=رهـجهـجت{\displaystyle g(q)=reject}يقال إن التكوين يرفض . تكوين معز(q)=∧{\displaystyle g(q)=\wedge }يُقال إن التكوين مقبول إذا كانت جميع التكوينات التي يمكن الوصول إليها في خطوة واحدة مقبولة، ورافض إذا كان بعض التكوينات التي يمكن الوصول إليها في خطوة واحدة رافضًا.ز(q)=∨{\displaystyle g(q)=\vee }يُقال إن الآلة تقبل عندما يكون هناك تكوين يمكن الوصول إليه في خطوة واحدة يقبل، وترفض عندما تكون جميع التكوينات التي يمكن الوصول إليها في خطوة واحدة رافضة (هذا هو نوع جميع الحالات في آلة تورينج الكلاسيكية باستثناء الحالة النهائية). يُقال إن الآلة تقبل سلسلة الإدخال w إذا كان التكوين الأولي للآلة (حالة الآلة ) هوq0{\displaystyle q_{0}}، يكون الرأس في الطرف الأيسر من الشريط، ويحتوي الشريط على w ) يقبل، ويرفض إذا كان التكوين الأولي يرفض.

لاحظ أنه من المستحيل أن يكون التكوين مقبولاً ورافضاً في نفس الوقت، ومع ذلك، قد لا تكون بعض التكوينات مقبولة ولا رافضة، وذلك بسبب إمكانية حدوث عمليات حسابية غير منتهية.

حدود الموارد

عند تحديد ما إذا كان تكوين جهاز الصراف الآلي يقبل أو يرفض عمليات السحب باستخدام التعريف المذكور أعلاه، ليس من الضروري دائمًا فحص جميع التكوينات التي يمكن الوصول إليها من التكوين الحالي. على وجه الخصوص، يمكن تصنيف التكوين الوجودي على أنه يقبل عمليات السحب إذا وُجد أن أي تكوين لاحق له يقبلها، ويمكن تصنيف التكوين الشامل على أنه يرفض عمليات السحب إذا وُجد أن أي تكوين لاحق له يرفضها.

يحدد جهاز الصراف الآلي لغة رسمية في الوقت المناسبت(ن){\displaystyle t(n)}إذا، عند أي مدخل بطول n ، يتم فحص التكوينات حتىت(ن){\displaystyle t(n)}تكفي الخطوات لتصنيف التكوين الأولي على أنه مقبول أو رافض. يحدد جهاز الصراف الآلي لغة في الفضاء.s(ن){\displaystyle s(n)}إذا تم فحص التكوينات التي لا تُعدّل خلايا الشريط بما يتجاوزs(ن){\displaystyle s(n)}الخلية من اليسار كافية.

لغة يتم تحديدها بواسطة جهاز صراف آلي في الوقت المناسبج⋅ت(ن){\displaystyle c\cdot t(n)}لبعض الثوابتج>0{\displaystyle c>0}يقال إنه في الفصلأتيأنامهـ(ت(ن)){\displaystyle {\mathsf {ATIME}}(t(n))}ولغة تُحدد في الفضاءج⋅s(ن){\displaystyle c\cdot s(n)}يقال إنه في الفصلأSPأجهـ(s(ن)){\displaystyle {\mathsf {ASPACE}}(s(n))}.

مثال

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

تقوم هذه الآلة بتحديد الصيغ المنطقية الكمية في الوقت المناسبن2{\displaystyle n^{2}}والمساحةن{\displaystyle n}.

يمكن اعتبار مشكلة الإرضاء البولياني حالة خاصة حيث يتم تحديد جميع المتغيرات كميًا وجوديًا، مما يسمح بعدم الحتمية العادية، التي تستخدم التفرع الوجودي فقط، بحلها بكفاءة.

فئات التعقيد ومقارنتها بآلات تورينج الحتمية

تُعد فئات التعقيد التالية مفيدة لتحديدها لأجهزة الصراف الآلي:

  • أP=⋃ك>0أتيأنامهـ(نك){\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}هل اللغات قابلة للتقرير في وقت متعدد الحدود؟
  • أPSPأجهـ=⋃ك>0أSPأجهـ(نك){\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}هل اللغات قابلة للتقرير في فضاء متعدد الحدود؟
  • أهـXPتيأنامهـ=⋃ك>0أتيأنامهـ(2نك){\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}هل اللغات قابلة للتقرير في وقت أسي؟

هذه التعريفات مشابهة لتعريفات P و PSPACE و EXPTIME ، مع الأخذ في الاعتبار الموارد التي يستخدمها جهاز الصراف الآلي بدلاً من آلة تورينج الحتمية. وقد أثبت تشاندرا وكوزين وستوكمير [ 3 ] أنه بالنسبة لجميعو(ن)≥سجل⁡(ن){\displaystyle f(n)\geq \log(n)}وز(ن)≥سجل⁡(ن){\displaystyle g(n)\geq \log(n)}:

  • أSPأجهـ(و(ن))=⋃ج>0دتيأنامهـ(2جو(ن))=دتيأنامهـ(2يا(و(ن))){\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}
  • أتيأنامهـ(ز(ن))⊆دSPأجهـ(ز(ن)){\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}
  • شمالSPأجهـ(ز(ن))⊆⋃ج>0أتيأنامهـ(ج×ز(ن)2)،{\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}

بخاصة:

  • ALOGSPACE = P
  • AP = PSPACE
  • مساحة التطبيق = وقت التجربة
  • AEXPTIME = EXPSPACE

يتم التعبير عن شكل أكثر عمومية لهذه العلاقات من خلال فرضية الحوسبة المتوازية .

التناوب المحدود

تعريف

آلة تورينغ المتناوبة ذات k تناوب هي آلة تورينغ متناوبة تنتقل من حالة وجودية إلى حالة شاملة أو العكس بما لا يزيد عن k − 1 مرة. (هي آلة تورينغ متناوبة تُقسّم حالاتها إلى k مجموعة. الحالات في المجموعات ذات الأرقام الزوجية شاملة، والحالات في المجموعات ذات الأرقام الفردية وجودية (أو العكس). لا يوجد في الآلة أي انتقالات بين حالة في المجموعة i وحالة في المجموعة j < i .)

أتيأنامهـ(ج،ج)=Σجتيأنامهـ(ج){\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}هل فئة اللغات قابلة للتقرير في وقتو∈ج{\displaystyle f\in C}بواسطة آلة تبدأ في حالة وجودية وتتناوب على الأكثرج-1{\displaystyle j-1}مرات. يُطلق عليه المستوى j منتيأنامهـ(ج){\displaystyle {\mathsf {TIME}}(C)}تَسَلسُل.

جoأتيأنامهـ(ج،ج)=Πجتيأنامهـ(ج){\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}يتم تعريفها بنفس الطريقة، ولكن بدءًا من حالة عالمية؛ وهي تتكون من مكملات اللغات فيأتيأنامهـ(و،ج){\displaystyle {\mathsf {ATIME}}(f,j)}.

أSPأجهـ(ج،ج)=ΣجSPأجهـ(ج){\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}يتم تعريفها بشكل مماثل للحسابات ذات المساحة المحدودة.

مثال

لنفترض مسألة تصغير الدائرة : إذا كانت لدينا دائرة A تحسب دالة منطقية f وعدد n ، فهل توجد دائرة أخرى تحتوي على n بوابة على الأكثر وتحسب نفس الدالة f ؟ يمكن لآلة تورينج المتناوبة، ذات التناوب الواحد، والتي تبدأ من حالة وجودية، حل هذه المسألة في وقت متعدد الحدود (عن طريق تخمين دائرة B تحتوي على n بوابة على الأكثر ، ثم الانتقال إلى حالة شاملة، وتخمين مدخل، والتحقق من أن خرج B عند هذا المدخل يطابق خرج A عند هذا المدخل).

دمج الفصول الدراسية

يقال إن التسلسل الهرمي ينهار إلى المستوى j إذا كانت كل لغة في المستوى jك≥ج{\displaystyle k\geq j}من التسلسل الهرمي يكون في مستواه j .

كنتيجة طبيعية لنظرية إيمرمان-سيليبسيني ، ينهار التسلسل الهرمي للفضاء اللوغاريتمي إلى مستواه الأول. [ 4 ] وكنتيجة طبيعية لـSPأجهـ(و){\displaystyle {\mathsf {SPACE}}(f)}ينهار التسلسل الهرمي إلى مستواه الأول عندماو=Ω(سجل){\displaystyle f=\Omega (\log )}يمكن بناء الفضاء .

حالات خاصة

يمكن لآلة تورينج المتناوبة، التي تعمل في زمن متعدد الحدود مع k من التناوبات، وتبدأ في حالة وجودية (أو عالمية على التوالي)، أن تحل جميع المسائل في الفئة.Σكص{\displaystyle \Sigma _{k}^{p}}(على التوالى،Πكص{\displaystyle \Pi _{k}^{p}}[ 5 ] يُشار إلى هذه الفئات أحيانًا بـΣكP{\displaystyle \Sigma _{k}{\rm {P}}}وΠكP{\displaystyle \Pi _{k}{\rm {P}}}على التوالي. راجع مقال التسلسل الهرمي متعدد الحدود لمزيد من التفاصيل.

ومن الحالات الخاصة الأخرى للتسلسلات الزمنية التسلسل الهرمي اللوغاريتمي .

مراجع

  1. ↑ شاندرا، أشوك ك.؛ ستوكمير، لاري ج. (1976). "التناوب". وقائع الندوة السابعة عشرة لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . هيوستن، تكساس. ص 98-108 . doi : 10.1109/SFCS.1976.4 . 
  2. ↑ كوزين، د. (1976). "حول التوازي في آلات تورينج". وقائع الندوة السابعة عشرة لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . هيوستن، تكساس. ص 89-97 . doi : 10.1109/SFCS.1976.20 . hdl : 1813/7056 . 
  3. 1 2 تشاندرا، أشوك ك.؛ كوزين، ديكستر س.؛ ستوكمير، لاري ج. (1981). "التناوب" (ملف PDF) . مجلة ACM . 28 (1): 114-133 . doi : 10.1145/322234.322243 . S2CID 238863413. مؤرشف من النسخة الأصلية (ملف PDF) في 12 أبريل 2016. 
  4. ↑ إيمرمان، نيل (1988). "الفضاء غير الحتمي مغلق تحت التتميم" (ملف PDF) . مجلة SIAM للحوسبة . 17 (5): 935-938 . CiteSeerX 10.1.1.54.5941 . doi : 10.1137/0217058 . 
  5. ^ كوزين ، ديكستر (2006). نظرية الحساب . سبرينغر-فيرلاغ . ص. 58 . رقم ISBN  9781846282973.

للمزيد من القراءة

  • مايكل سيبسر (2006). مقدمة في نظرية الحوسبة (  الطبعة الثانية). دار نشر PWS. رقم ISBN 978-0-534-95097-2.القسم 10.3: التناوب، الصفحات  380-386.
  • كريستوس باباديميتريو (1993). التعقيد الحسابي (  الطبعة الأولى). أديسون ويسلي. ISBN 978-0-201-53082-7.القسم 16.2: التناوب، الصفحات  399-401.
  • بالكازار، خوسيه لويس؛ دياز، جوزيب؛ جابارو، يواكيم (1990)، “التناوب” ، في بالكازار، خوسيه لويس؛ دياز، جوزيب؛ غابارو ، يواكيم (محرران)، التعقيد الهيكلي II ، برلين، هايدلبرغ: سبرينغر، الصفحات من 63 إلى 96، دوى : 10.1007 / 978-3-642-75357-2_4 ، ISBN  978-3-642-75357-2تم الاطلاع عليه بتاريخ 19-05-2025
  • باخادِر خوسينوف؛ أنيل نيرود (2012). نظرية الأوتوماتا وتطبيقاتها . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-1-4612-0171-7.