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

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

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

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

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

1. ↑ Sipser, Michael (2005). Introduction to the Theory of Computation. Thomson Course Technology. p. 148. ISBN 0-534-95097-3.
2. ↑ Papadimitriou, Christos (1994). Computational Complexity. Addison-Wesley. p. 53. ISBN 0-201-53082-1.
3. ↑ Martin, John (2010). Introduction to Languages and the Theory of Computation. McGraw Hill. pp. 243–246. ISBN 978-0071289429.