Máy Turing nhiều băng
Máy Turing nhiều băng có nhiều băng trong đó mỗi băng được truy cập bằng một đầu riêng biệt. Mỗi đầu có thể di chuyển độc lập với các đầu khác. Ban đầu đầu vào nằm trên băng 1 và những đầu vào khác để trống. Lúc đầu, băng đầu tiên bị chiếm bởi đầu vào và các băng khác được giữ trống. Tiếp theo, máy đọc các ký hiệu liên tiếp dưới đầu của nó và TM in một ký hiệu trên mỗi băng và di chuyển các đầu của nó.
Máy Turing nhiều băng có thể được mô tả chính thức như một bộ 6 bộ (Q, X, B, δ, q 0 , F) trong đó -
Q là một tập hợp hữu hạn các trạng thái
X là bảng chữ cái băng
B là biểu tượng trống
δ là một quan hệ về trạng thái và biểu tượng trong đó
δ: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift}) k
ở đó ở đâu k số lượng băng
q0 là trạng thái ban đầu
F là tập hợp các trạng thái cuối cùng
Note - Mỗi máy Turing nhiều băng đều có một máy Turing một băng tương đương.