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

ماشین تورینگ چند نواره مانند ماشین تورینگ های معمول است که به جای یک نوار چندین نوار دارد .هر نوار کلاهک مخصوص به خود را، برای عمل خواندن و نوشتن، دارد .در ابتدا، رشتهٔ ورودی بر روی نوار اول نمایش داده می شود و بقیه نوارها خالی هستند .
Q {\displaystyle Q}   مجموعه ای متناهی از حالات است .
Γ {\displaystyle \Gamma }   مجموعه ای متناهی ازالفبای نوار است
s ∈ Q {\displaystyle s\in Q}   حالت اولیه است .
b ∈ Γ {\displaystyle b\in \Gamma }  برای نمایش یک فاصلهٔ خالی است.
F ⊆ Q {\displaystyle F\subseteq Q}   مجموعهٔ حالات پایانی یا حالت مورد پذیرش است .
δ : Q × Γ k → Q × ( Γ × { L , R , S } ) k {\displaystyle \delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{L,R,S\})^{k}}   تابعی جزئی به نام تابع انتقال است که در آن K برابر باتعداد نوارها ،L نشان دهنده انتقال به چپ ، R نشان دهنده انتقال به راست و s نشان دهنده ثابت بودن است.
به نظر می رسد که این مدل از ماشین های تورینگ قویتر از مدل های تک نواره هستند در حالی که چنین نیست و هر ماشین تورینگ چند نواره ای، فارغ از تعداد نوارهای آن ، می تواند توسط یک ماشین تورینگ تک نواره با درجهٔ پیچیدگی بیشتر شبیه سازی شود.
بنابراین ماشین تورینگ های چند نواره نمیتوانند توابع ای بیش از آنچه ماشین های تورینگ چند نواره محاسبه میکنند ،محاسبه کنند و هیچ کدام از کلاس های پیچیدگی محاسباتی (مانندکلاس P ) با تغییر یک ماشین تورینگ چند نواره به تک نواره تحت تأثیر قرار نمی گیرند.
یک ماشین تورینگ چند نواره می تواند به صورت یک ۶ تائی به فرم M = ⟨ Q , Γ , s , b , F , δ ⟩ {\displaystyle M=\langle Q,\Gamma ,s,b,F,\delta \rangle }   تعریف شود که در آن :