ماشین تورینگ چندمسیره
ماشین تورینگ چندمسیره (به انگلیسی: Multi-track Turing machine) یا چندمجرایی نوع خاصی از ماشین تورینگ چندنواره است. در یک ماشین تورینگ استاندارد با n نوار ،n کلاهک به صورت مستقل در امتداد n مسیر حرکت میکنند. در یک ماشین تورینگ چند مجرایی با n مجرا یک کلاهک روی تمام مجراها عمل خواندن و نوشتن را به صورت همزمان انجام میدهد. هر موقعیت در این ماشین تورینگ شامل n نماد از حروف الفبا میباشد. این ماشین تورینگ، معادل ماشین تورینگ استاندارد است و زبانهای شمارا را، که به صورت بازگشتی تعریف شدهاند، میپذیرد.
تعریف علمی
یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت
- مجموعه متناهی از حالتها است.
- مجموعهٔ متناهی از نمادها است که الفبای پشته نام دارد.
- نشان دهنده حالت اولیه است.
- مجموعه حالتهای پایانی یا حالتهای مورد پذیرش ماشین است.
- رابطهای بین حالتهای ماشین و نمادها است که انتقال نام دارد.
- که.
معادل بودن با ماشین تورینگ استاندارد
این اثبات معادل بودن ماشین تورینگ ۲مجرایی را با ماشین تورینگ استاندارد نشان میدهد و قابل تعمیم به ماشین تورینگ n مجرایی است.
با در نظر گرفتن زبان شمارای L، ماشین استاندارد M را اینگونه تعریف میکنیم:
اگر همهٔ مجراهای 'M، به جز اولین مجرای آن، حذف شوند، به وضوح دیده میشود که M' و M با هم معادل هستند.
اگر بخواهیم یک ماشین تورینگ تک مجرایی معادل با ماشین تورینگ ۲ مجرایی بسازیم، الفبای آن به صورت زوج مرتب تعریف میشود.
نماد a از ماشین تورینگ 'M به شکل یک زوج مراتب [x,y] در ماشین تورینگ M تعریف میشود.
ماشین تورینگ تک نوارهٔ معادل به صورت زیر تعریف میشود:
M=
جستارهای وابسته
منابع
- Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271