多带图灵机

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

\delta : Q\times\Gamma^k \to Q \times \Gamma^k \times \{L, R\}^k

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

\delta(q, x_1, x_2, \ldots, x_k) = (q', x'_1, x'_2, \ldots, x'_k, m_1, m_2, \ldots, m_k)

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

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