آلة تورينج متعددة الأشرطة

الموسوعة الحرة

آلة تورينج متعددة الأشرطة هي نوع من آلات تورينج تستخدم عدة أشرطة. يحتوي كل شريط على رأس خاص به للقراءة والكتابة. في البداية، تظهر المدخلات على الشريط 1، بينما تبدأ الأشرطة الأخرى فارغة. [ 1 ]

يبدو هذا النموذج بديهيًا أكثر قوة من نموذج الشريط الواحد، ولكن يمكن محاكاة أي آلة متعددة الأشرطة - مهما كان عدد أشرطتها - بواسطة آلة أحادية الشريط باستخدام وقت حسابي إضافي بمقدار تربيعي فقط . [ 2 ] أي أن أي لغة يمكن تحديدها في زمن O( t ( n )) بواسطة آلة تورينج متعددة الأشرطة يمكن تحديدها في زمن O( t² ( n )) بواسطة آلة تورينج أحادية الشريط.

وبالتالي، لا تستطيع آلات الشريط المتعدد حساب وظائف أكثر من آلات الشريط الواحد، [ 3 ] ولا تتأثر أي من فئات التعقيد القوية (مثل الوقت متعدد الحدود ) بالتغيير بين آلات الشريط الواحد وآلات الشريط المتعدد.

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

أك{\displaystyle k}يمكن تعريف آلة تورينج الشريطية رسميًا على أنها مجموعة سباعيةم=⟨سؤال،Γ،ب،Σ،دلتا،q0،F⟩{\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }، باتباع ترميز آلة تورينج :

  • Γ{\displaystyle \Gamma }هي مجموعة محدودة وغير فارغة من رموز الأبجدية الشريطية ؛
  • ب∈Γ{\displaystyle b\in \Gamma }هو الرمز الفارغ (الرمز الوحيد المسموح بظهوره على الشريط بشكل لا نهائي في أي خطوة أثناء الحساب)؛
  • Σ⊆Γ∖{ب}{\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}هي مجموعة رموز الإدخال ، أي مجموعة الرموز المسموح بظهورها في محتويات الشريط الأولية؛
  • سؤال{\displaystyle Q}هي مجموعة محدودة وغير فارغة من الحالات ؛
  • q0∈سؤال{\displaystyle q_{0}\in Q}هي الحالة الابتدائية ؛
  • F⊆سؤال{\displaystyle F\subseteq Q}هي مجموعة الحالات النهائية أو حالات القبول . ويُقال إن محتويات الشريط الأولية قد تم قبولها بواسطةم{\displaystyle M}إذا توقف في نهاية المطاف في حالة منF{\displaystyle F}.
  • دلتا:(سؤال∖F)×Γك→سؤال×Γك×{ل،R}ك{\displaystyle \delta :(Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}} هي دالة جزئية تسمى دالة الانتقال ، حيث L هي الإزاحة إلى اليسار، و R هي الإزاحة إلى اليمين.

أك{\displaystyle k}آلة تورينج الشريطيةم{\displaystyle M}، أينك{\displaystyle k}يمثل عدد الأشرطة المخصصة، ويتم حسابه على النحو التالي.م{\displaystyle M}يبدأ في حالته الأوليةq0{\displaystyle q_{0}}يتم تعريف ذلك من خلال احتواء جميع الأشرطة على رأس واحد يبدأ من أقصى اليسار، بالإضافة إلى مدخلw=w1w2...wن∈Σ*{\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}في أقصى اليسارن{\displaystyle n}مواقع الشريط الأول، وجميع الرموز الأخرى لكل شريط هي الرمز الفارغ المحدد بواسطةب{\displaystyle b}تُنفذ خطوة للآلة بتقييم دالة الانتقال. ويتم ذلك من خلال أخذ الحالة الحالية في الاعتبار.qأنا∈سؤال{\displaystyle q_{i}\in Q}ومجموعة الرموز الأبجدية التي تقع فوقها الرؤوس، والمُشار إليها بـΓك{\displaystyle \Gamma ^{k}}تأخذ دالة الانتقال كلا هذين المعاملين وتُخرج الأشياء الثلاثة الضرورية للانتقال: الحالة الجديدةqج∈سؤال{\displaystyle q_{j}\in Q}الذي - التيم{\displaystyle M}يتحول إلى مجموعة جديدة من رموز الأبجديةΓك{\displaystyle \Gamma ^{k}}أن كل واحد منك{\displaystyle k}ستكتب الرؤوس إلى خلاياها الخاصة، ومجموعة من تعليمات التحويل{ل،R}ك{\displaystyle \{L,R\}^{k}}سيُحدد ذلك لكل رأس الاتجاه الذي يجب أن يتحرك إليه (يسارًا أو يمينًا خلية واحدة) بعد كتابة الرموز الجديدة. وتستمر دالة الانتقال في التكرار حتىم{\displaystyle M}يدخل في حالة نهائية تنتمي إلى المجموعةF{\displaystyle F}وعند هذه النقطة يتوقف.

آلة تورينج ذات المكدس المزدوج

تحتوي آلات تورينج ذات المكدسين على مدخل للقراءة فقط وشريطين للتخزين. إذا تحرك رأس القراءة/الكتابة إلى اليسار على أي من الشريطين، تتم طباعة صفحة فارغة على ذلك الشريط، ولكن يمكن طباعة رمز واحد من "مكتبة".

انظر أيضاً

مراجع

  1. ↑ سيبسر، مايكل (2005). مقدمة في نظرية الحوسبة . تومسون كورس تكنولوجي. ص  148. ISBN 0-534-95097-3.
  2. ↑ باباديميتريو ، كريستوس (1994). التعقيد الحسابي . أديسون-ويسلي. ص 53. ISBN  0-201-53082-1.
  3. ↑ مارتن، جون (2010). مقدمة في اللغات ونظرية الحوسبة . ماكجرو هيل. الصفحات 243-246 . ISBN  978-0071289429.