查看“︁多带图灵机”︁的源代码

{{unreferenced|time=2018-09-18T02:49:42+00:00}}
'''多带图灵机'''和[[图灵机]]类似，唯一的不同在于它可以有 <math>k > 1</math> 条纸带，每条纸带上
都有一个读写头。其状态转移函数 <math>\delta</math> 修改为：
<center><math>
\delta : Q\times\Gamma^k \to Q \times \Gamma^k \times \{L, R\}^k
</math></center>
此处 <math>k</math> 是带子的数目。表达式
<center><math>
\delta(q, x_1, x_2, \ldots, x_k) = (q', x'_1, x'_2, \ldots, x'_k, m_1, m_2, \ldots, m_k)
</math></center>
其中 <math>m_i</math> = L 或 R，
说明若机器处于状态 <math>q</math>，
读写头 <math>1, 2, \ldots, k</math> 所读出的符号分别为<math>x_1, x_2,\ldots, x_k</math>，
则转移到新状态 <math>q'</math>，
将读写头 <math>1, 2, \ldots, k</math> 下的符号分别修改为 <math>x'_1, x'_2,\ldots, x'_k</math> ，
并将读写头 <math>i</math> 按照 <math>m_i</math> 所指示的方向移动，
<math>m_i = L</math> 读写头 <math>i</math> 向左移，
<math>m_i = R</math> 读写头 <math>i</math> 向右移。

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

[[Category:图灵机]]