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

ماشین تورینگ چندمسیره (به انگلیسی: Multi-track Turing machine) یا چندمجرایی نوع خاصی از ماشین تورینگ چندنواره است. در یک ماشین تورینگ استاندارد با n نوار ،n کلاهک به صورت مستقل در امتداد n مسیر حرکت می‌کنند. در یک ماشین تورینگ چند مجرایی با n مجرا یک کلاهک روی تمام مجراها عمل خواندن و نوشتن را به صورت هم‌زمان انجام می‌دهد. هر موقعیت در این ماشین تورینگ شامل n نماد از حروف الفبا می‌باشد. این ماشین تورینگ، معادل ماشین تورینگ استاندارد است و زبان‌های شمارا را، که به صورت بازگشتی تعریف شده‌اند، می‌پذیرد.

تعریف علمی

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

• $Q$ مجموعه متناهی از حالت‌ها است.
• $\Sigma$مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
• $\Gamma \in Q$
• $q_{0}\in Q$ نشان دهنده حالت اولیه است.
• $F\subseteq Q$ مجموعه حالت‌های پایانی یا حالت‌های مورد پذیرش ماشین است.
• $\delta \subseteq \left(Q\backslash F\times \Sigma \right)\times \left(Q\times \Sigma \times d\right)$ رابطه‌ای بین حالت‌های ماشین و نمادها است که انتقال نام دارد.
• $\delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)$ که $d\in \{L,R\}$.

معادل بودن با ماشین تورینگ استاندارد

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

• $M\subseteq M'$

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

• $M'\subseteq M$

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