多带图灵机维基百科,自由的 encyclopedia 多带图灵机和图灵机类似,唯一的不同在于它可以有 k > 1 {\displaystyle k>1} 条纸带,每条纸带上 都有一个读写头。其状态转移函数 δ {\displaystyle \delta } 修改为: δ : Q × Γ k → Q × Γ k × { L , R } k {\displaystyle \delta :Q\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}} 此条目没有列出任何参考或来源。 (2018年9月18日) 此处 k {\displaystyle k} 是带子的数目。表达式 δ ( q , x 1 , x 2 , … , x k ) = ( q ′ , x 1 ′ , x 2 ′ , … , x k ′ , m 1 , m 2 , … , m k ) {\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})} 其中 m i {\displaystyle m_{i}} = L 或 R, 说明若机器处于状态 q {\displaystyle q} , 读写头 1 , 2 , … , k {\displaystyle 1,2,\ldots ,k} 所读出的符号分别为 x 1 , x 2 , … , x k {\displaystyle x_{1},x_{2},\ldots ,x_{k}} , 则转移到新状态 q ′ {\displaystyle q'} , 将读写头 1 , 2 , … , k {\displaystyle 1,2,\ldots ,k} 下的符号分别修改为 x 1 ′ , x 2 ′ , … , x k ′ {\displaystyle x'_{1},x'_{2},\ldots ,x'_{k}} , 并将读写头 i {\displaystyle i} 按照 m i {\displaystyle m_{i}} 所指示的方向移动, m i = L {\displaystyle m_{i}=L} 读写头 i {\displaystyle i} 向左移, m i = R {\displaystyle m_{i}=R} 读写头 i {\displaystyle i} 向右移。 可以证明,对于任意一个多带图灵机 M {\displaystyle M} ,存在一个单带图灵机 M ′ {\displaystyle M'} ,满足 L ( M ) = L ( M ′ ) {\displaystyle L(M)=L(M')} 。
多带图灵机和图灵机类似,唯一的不同在于它可以有 k > 1 {\displaystyle k>1} 条纸带,每条纸带上 都有一个读写头。其状态转移函数 δ {\displaystyle \delta } 修改为: δ : Q × Γ k → Q × Γ k × { L , R } k {\displaystyle \delta :Q\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}} 此条目没有列出任何参考或来源。 (2018年9月18日) 此处 k {\displaystyle k} 是带子的数目。表达式 δ ( q , x 1 , x 2 , … , x k ) = ( q ′ , x 1 ′ , x 2 ′ , … , x k ′ , m 1 , m 2 , … , m k ) {\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})} 其中 m i {\displaystyle m_{i}} = L 或 R, 说明若机器处于状态 q {\displaystyle q} , 读写头 1 , 2 , … , k {\displaystyle 1,2,\ldots ,k} 所读出的符号分别为 x 1 , x 2 , … , x k {\displaystyle x_{1},x_{2},\ldots ,x_{k}} , 则转移到新状态 q ′ {\displaystyle q'} , 将读写头 1 , 2 , … , k {\displaystyle 1,2,\ldots ,k} 下的符号分别修改为 x 1 ′ , x 2 ′ , … , x k ′ {\displaystyle x'_{1},x'_{2},\ldots ,x'_{k}} , 并将读写头 i {\displaystyle i} 按照 m i {\displaystyle m_{i}} 所指示的方向移动, m i = L {\displaystyle m_{i}=L} 读写头 i {\displaystyle i} 向左移, m i = R {\displaystyle m_{i}=R} 读写头 i {\displaystyle i} 向右移。 可以证明,对于任意一个多带图灵机 M {\displaystyle M} ,存在一个单带图灵机 M ′ {\displaystyle M'} ,满足 L ( M ) = L ( M ′ ) {\displaystyle L(M)=L(M')} 。