Xrthnty

多带图灵机和图灵机类似，唯一的不同在于它可以有 k>1displaystyle k>1 条纸带，每条纸带上
都有一个读写头。其状态转移函数 δdisplaystyle delta 修改为：

δ:Q×Γk→Q×Γk×L,Rkdisplaystyle delta :Qtimes Gamma ^kto Qtimes Gamma ^ktimes L,R^k

此处 kdisplaystyle k 是带子的数目。表达式

δ(q,x1,x2,…,xk)=(q′,x1′,x2′,…,xk′,m1,m2,…,mk)displaystyle delta (q,x_1,x_2,ldots ,x_k)=(q',x'_1,x'_2,ldots ,x'_k,m_1,m_2,ldots ,m_k)

其中 midisplaystyle m_i = L 或 R，
说明若机器处于状态 qdisplaystyle q，
读写头 1,2,…,kdisplaystyle 1,2,ldots ,k 所读出的符号分别为x1,x2,…,xkdisplaystyle x_1,x_2,ldots ,x_k，
则转移到新状态 q′displaystyle q'，
将读写头 1,2,…,kdisplaystyle 1,2,ldots ,k 下的符号分别修改为 x1′,x2′,…,xk′displaystyle x'_1,x'_2,ldots ,x'_k ，
并将读写头 idisplaystyle i 按照 midisplaystyle m_i 所指示的方向移动，
mi=Ldisplaystyle m_i=L 读写头 idisplaystyle i 向左移，
mi=Rdisplaystyle m_i=R 读写头 idisplaystyle i 向右移。

可以证明，对于任意一个多带图灵机 Mdisplaystyle M ，存在一个单带图灵机 M′displaystyle M' ，满足 L(M)=L(M′)displaystyle L(M)=L(M')。