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

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

 تعریف علمی 
یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت 
تعریف می‌شود که در آن:
  مجموعه متناهی از حالت‌ها است.
 مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.

  نشان دهنده حالت اولیه است.
  مجموعه حالت‌های پایانی یا حالت‌های مورد پذیرش ماشین است.
  رابطه‌ای بین حالت‌های ماشین و نمادها است که انتقال نام دارد.
  که .

 معادل بودن با ماشین تورینگ استاندارد 
این اثبات معادل بودن ماشین تورینگ ۲مجرایی را با ماشین تورینگ استاندارد نشان می‌دهد و قابل تعمیم به ماشین تورینگ n مجرایی است.
با در نظر گرفتن زبان شمارای L، ماشین استاندارد M را اینگونه تعریف می‌کنیم: . این ماشین زبان L را می‌پذیرد.
حال، 'M را یک ماشین تورینگ ۲-مجرایی فرض می‌کنیم. برای اثبات معادل بودن، باید ثابت شود M  M و M'  M.


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


اگر بخواهیم یک ماشین تورینگ تک مجرایی معادل با ماشین تورینگ ۲ مجرایی بسازیم، الفبای آن به صورت زوج مرتب تعریف می‌شود.
نماد a از ماشین تورینگ 'M به شکل یک زوج مراتب [x,y] در ماشین تورینگ M تعریف می‌شود.
ماشین تورینگ تک نوارهٔ معادل به صورت زیر تعریف می‌شود:
M=  که تابع انتقال آن برابر است با 

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

 منابع 

 Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. . Chapter 8.6: Multitape Machines: pp 269-271


رده:ماشین تورینگ