เครื่องทัวริงแบบมัลติแทร็กเป็นเครื่องทัวริงแบบมัลติเทปชนิดหนึ่งโดยเฉพาะ

ในเครื่องทัวริงแบบเทป n เทปมาตรฐาน หัวอ่าน n หัวจะเคลื่อนที่อย่างอิสระไปตามแทร็ก n แทร็ก ในเครื่องทัวริงแบบแทร็ก n หัวอ่านหนึ่งหัวจะอ่านและเขียนบนทุกแทร็กพร้อมกัน ตำแหน่งเทปในเครื่องทัวริงแบบแทร็ก n หัวจะบรรจุสัญลักษณ์ n ตัวจากตัวอักษรของเทป มันเทียบเท่ากับเครื่องทัวริง มาตรฐานและดังนั้นจึงยอมรับ ภาษาที่สามารถแจงนับได้แบบเวียนซ้ำได้อย่าง แม่นยำ

เครื่องจักรทัวริงแบบมัลติแทร็กที่มีเทป - สามารถนิยามอย่างเป็นทางการได้ว่าเป็นทูเพิล 6 ตัวโดยที่ ${\displaystyle n}$${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle Q}$เป็นเซตของสถานะที่มีจำนวนจำกัด
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$คือเซตจำกัดของสัญลักษณ์อินพุตซึ่งก็คือเซตของสัญลักษณ์ที่อนุญาตให้ปรากฏในเนื้อหาเทปเริ่มต้น
• ${\displaystyle \Gamma }$เป็นเซตจำกัดของสัญลักษณ์ตัวอักษรเทป ;
• ${\displaystyle q_{0}\in Q}$คือสถานะเริ่มต้น ;
• ${\displaystyle F\subseteq Q}$คือเซตของ สถานะ สุดท้ายหรือสถานะที่ยอมรับได้ ;
• ${\displaystyle \delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$เป็นฟังก์ชันบางส่วนที่เรียกว่าฟังก์ชันการเปลี่ยนผ่าน

บางครั้งอาจใช้สัญลักษณ์ โดยที่.${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$${\displaystyle d\in \{L,R\}}$

รูปแบบที่ไม่แน่นอนสามารถกำหนดได้โดยการแทนที่ฟังก์ชันการเปลี่ยนสถานะด้วยความสัมพันธ์การเปลี่ยนสถานะ ${\displaystyle \delta }$${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$

นี่จะเป็นการพิสูจน์ว่าเครื่องจักรทัวริงแบบสองแทร็กเทียบเท่ากับเครื่องจักรทัวริงมาตรฐาน สามารถขยายความไปสู่เครื่องจักรทัวริงแบบ n แทร็กได้ ให้ L เป็นภาษาที่แจงนับได้แบบเรียกซ้ำ ให้ M ' เป็นเครื่องจักรทัวริงมาตรฐานที่ยอมรับ L ให้M'เป็นเครื่องจักรทัวริงแบบสองแทร็ก ในการพิสูจน์⁠ ⁠จะต้องแสดงให้เห็นว่าและ. ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$${\displaystyle M=M'}$${\displaystyle M\subseteq M'}$${\displaystyle M'\subseteq M}$

• ${\displaystyle M\subseteq M'}$

หากไม่นับแทร็กที่สองแล้วMและM'จะมีความหมายเหมือนกันอย่างชัดเจน

• ${\displaystyle M'\subseteq M}$

ตัวอักษรเทปของเครื่องทัวริงแบบแทร็กเดียวที่เทียบเท่ากับเครื่องทัวริงแบบสองแทร็กประกอบด้วยคู่ลำดับสัญลักษณ์อินพุต a ของเครื่องทัวริงM'สามารถระบุได้ว่าเป็นคู่ลำดับ⁠ ⁠${\displaystyle [x,y]}$ของเครื่องทัวริงMเครื่องทัวริงแบบแทร็กเดียวคือ:

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$ด้วยฟังก์ชันการเปลี่ยนผ่าน${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

เครื่องนี้รองรับ L ด้วยเช่นกัน