آلة تورينج متعددة المسارات

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

في آلة تورينغ القياسية ذات n شريط، تتحرك n رأسًا بشكل مستقل على طول n مسارًا. أما في آلة تورينغ ذات n مسارًا، فيقرأ رأس واحد ويكتب على جميع المسارات في آنٍ واحد. يحتوي موضع الشريط في آلة تورينغ ذات n مسارًا على n رمزًا من أبجدية الشريط. وهي مكافئة لآلة تورينغ القياسية ، وبالتالي تقبل تحديدًا اللغات القابلة للتعداد التكراري .

آلة تورينج متعددة المسارات مع${\displaystyle n}$يمكن تعريف الأشرطة رسميًا على أنها مجموعة من 6 عناصر${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$، أين

• ${\displaystyle Q}$هي مجموعة محدودة من الحالات؛
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$هي مجموعة محدودة من رموز الإدخال ، أي مجموعة الرموز المسموح بظهورها في محتويات الشريط الأولية؛
• ${\displaystyle \Gamma }$هي مجموعة محدودة من رموز الأبجدية الشريطية ؛
• ${\displaystyle q_{0}\in Q}$هي الحالة الابتدائية ؛
• ${\displaystyle F\subseteq Q}$هي مجموعة الحالات النهائية أو المقبولة ؛
• ${\displaystyle \delta$ :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)} هي دالة جزئية تسمى دالة الانتقال .

يُشار إليه أحيانًا أيضًا باسم${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$، أين${\displaystyle d\in \{L,R\}}$.

يمكن تعريف متغير غير حتمي عن طريق استبدال دالة الانتقال${\displaystyle \delta }$عن طريق علاقة انتقالية${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$.

سيثبت هذا أن آلة تورينج ذات المسارين مكافئة لآلة تورينج القياسية. ويمكن تعميم ذلك على آلة تورينج ذات n مسار. ليكن L لغة قابلة للتعداد التكراري.${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$لتكن M' آلة تورينغ قياسية تقبل L. ولتكن M' آلة تورينغ ذات مسارين. المطلوب إثباته${\displaystyle M=M'}$يجب إثبات ذلك${\displaystyle M\subseteq M'}$و${\displaystyle M'\subseteq M}$.

• ${\displaystyle M\subseteq M'}$

إذا تم تجاهل المسار الثاني، فإن M و M' متكافئتان بشكل واضح.

• ${\displaystyle M'\subseteq M}$

تتكون أبجدية الشريط لآلة تورينج أحادية المسار، المكافئة لآلة تورينج ثنائية المسار، من زوج مرتب . ويمكن تحديد رمز الإدخال a لآلة تورينج M' على أنه زوج مرتب .${\displaystyle [x,y]}$آلة تورينج M. آلة تورينج ذات المسار الواحد هي:

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$باستخدام دالة الانتقال${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

تقبل هذه الآلة أيضًا مقاس L.

• توماس أ. سودكامب (2006). اللغات والآلات، الطبعة الثالثة. أديسون-ويسلي. ISBN 0-321-32221-5الفصل 8.6: آلات التسجيل متعددة الأشرطة: الصفحات 269-271