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

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

تعریف علمی

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

• $Q$ مجموعه متناهی از حالت‌ها است.
• $\mathrm{\Sigma }$مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
• $\mathrm{\Gamma }\in Q$
• $q_0\in Q$ نشان دهنده حالت اولیه است.
• $F\subseteq Q$ مجموعه حالت‌های پایانی یا حالت‌های مورد پذیرش ماشین است.
• $\delta \subseteq (Q\mathrm{\setminus }F\times \mathrm{\Sigma })\times (Q\times \mathrm{\Sigma }\times d)$ رابطه‌ای بین حالت‌های ماشین و نمادها است که انتقال نام دارد.
• $\delta (Q_i,[x_1,x_2...x_n])=(Q_j,[y_1,y_2...y_n],d)$ که $d\in \{L,R\}$.

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

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

• $M\subseteq M^{\prime }$

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

• $M^{\prime }\subseteq M$

اگر بخواهیم یک ماشین تورینگ تک مجرایی معادل با ماشین تورینگ ۲ مجرایی بسازیم، الفبای آن به صورت زوج مرتب تعریف می‌شود. نماد a از ماشین تورینگ 'M به شکل یک زوج مراتب [x,y] در ماشین تورینگ M تعریف می‌شود. ماشین تورینگ تک نوارهٔ معادل به صورت زیر تعریف می‌شود: M= $⟨Q,\mathrm{\Sigma }\times B,\mathrm{\Gamma }\times \mathrm{\Gamma },{\delta }^{\prime },q_0,F⟩$ که تابع انتقال آن برابر است با $\delta (q_i,[x_1,x_2])={\delta }^{\prime }(q_i,[x_1,x_2])$

جستارهای وابسته

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

منابع

• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. الگو:ISBN. Chapter 8.6: Multitape Machines: pp 269-271
• الگو:یادکرد-ویکی