Máy Turing nhiều rãnh
Máy Turing nhiều rãnh, một loại cụ thể của Máy Turing nhiều băng, chứa nhiều rãnh nhưng chỉ một đầu băng đọc và ghi trên tất cả các rãnh. Ở đây, một đầu băng đơn đọc n ký hiệu từntheo dõi ở một bước. Nó chấp nhận các ngôn ngữ có thể liệt kê đệ quy giống như một Máy Turing băng đơn một rãnh thông thường chấp nhận.
Máy Turing nhiều rãnh có thể được mô tả chính thức như một bộ 6 bộ (Q, X, ∑, δ, 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
∑ là bảng chữ cái đầu vào
δ là một quan hệ về trạng thái và biểu tượng trong đó
δ (Q i , [a 1 , a 2 , a 3 , ....]) = (Q j , [b 1 , b 2 , b 3 , ....], Left_shift hoặc Right_shift)
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 - Đối với mọi Máy Turing đơn S, có một Máy Turing đa rãnh tương đương M như vậy mà L(S) = L(M).