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

یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت ${\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 }$. این ماشین زبان L را می‌پذیرد. حال، 'M را یک ماشین تورینگ ۲-مجرایی فرض می‌کنیم. برای اثبات معادل بودن، باید ثابت شود M ${\displaystyle \subseteq }$ M و M' ${\displaystyle \subseteq }$ M.

• ${\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 }$ که تابع انتقال آن برابر است با ${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

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

• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271
• مشارکت‌کنندگان ویکی‌پدیا. «Multi-track Turing machine». در دانشنامهٔ ویکی‌پدیای انگلیسی.