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

ماشین تورینگ چند نواره مانند ماشین تورینگ‌های معمول است که به جای یک نوار چندین نوار دارد .هر نوار کلاهک مخصوص به خود را، برای عمل خواندن و نوشتن، دارد .در ابتدا، رشتهٔ ورودی بر روی نوار اول نمایش داده می‌شود و بقیه نوارها خالی‌ هستند .

به نظر می‌رسد که این مدل از ماشین‌های تورینگ قویتر از مدل‌های تک نواره هستند در حالی‌ که چنین نیست و هر ماشین تورینگ چند نواره‌ای، فارغ از تعداد نوارهای آن‌، می‌تواند توسط یک ماشین تورینگ تک نواره با درجهٔ پیچیدگی‌ بیشتر شبیه سازی شود.

بنابراین ماشین تورینگ‌های چند نواره نمیتوانند توابع ای بیش از آنچه ماشین‌های تورینگ‌ چند نواره محاسبه میکنند ،محاسبه کنند و هیچ‌کدام از کلاس‌های پیچیدگی محاسباتی (مانندکلاس P ) با تغییر یک ماشین تورینگ چند نواره به تک نواره تحت تأثیر قرار نمی‌گیرند.

تعریف علمی‌

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

• $Q$ مجموعه‌ای متناهی از حالات است .
• $\mathrm{\Gamma }$ مجموعه‌ای متناهی ازالفبای نوار است
• $s\in Q$ حالت اولیه است .
• $b\in \mathrm{\Gamma }$برای نمایش یک فاصلهٔ خالی است.
• $F\subseteq Q$ مجموعهٔ حالات پایانی یا حالت مورد پذیرش است .
• $\delta :Q\times {\mathrm{\Gamma }}^k\to Q\times (\mathrm{\Gamma }\times \{L,R,S\}{)}^k$ تابعی جزئی‌ به نام تابع انتقال است که در آن‌K برابر باتعداد نوارها ،L نشان دهنده انتقال‌ به چپ ، R نشان دهنده انتقال‌ به راست و s نشان دهنده ثابت بودن است.

ماشین تورینگ با ۲ پشته

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

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

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