ماشین تورینگ چندمسیره

یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle Q}$
  مجموعه متناهی از حالت‌ها است.
• ${\displaystyle \Sigma }$
  مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
• ${\displaystyle \Gamma \in Q}$
• ${\displaystyle q_{0}\in Q}$
  نشان دهنده حالت اولیه است.
• ${\displaystyle F\subseteq Q}$
  مجموعه حالت‌های پایانی یا حالت‌های مورد پذیرش ماشین است.
• ${\displaystyle \delta \subseteq \left(Q\backslash F\times \Sigma \right)\times \left(Q\times \Sigma \times d\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\}}$
  .

این اثبات معادل بودن ماشین تورینگ ۲مجرایی را با ماشین تورینگ استاندارد نشان می‌دهد و قابل تعمیم به ماشین تورینگ n مجرایی است. با در نظر گرفتن زبان شمارای L، ماشین استاندارد M را اینگونه تعریف می‌کنیم: ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$

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

اگر همهٔ مجراهای 'M، به جز اولین مجرای آن، حذف شوند، به وضوح دیده می‌شود که M' و M با هم معادل هستند.

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

اگر بخواهیم یک ماشین تورینگ تک مجرایی معادل با ماشین تورینگ ۲ مجرایی بسازیم، الفبای آن به صورت زوج مرتب تعریف می‌شود. نماد a از ماشین تورینگ 'M به شکل یک زوج مراتب [x,y] در ماشین تورینگ M تعریف می‌شود. ماشین تورینگ تک نوارهٔ معادل به صورت زیر تعریف می‌شود: M= ${\displaystyle \langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$

• ماشین محاسبه تورینگ

• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271