Automata Theory 简明教程

具有半无限磁带的图灵机具有左端但没有右端。左端用结束标记限制。

它是一条两轨磁带 -

无限长度的输入字符串最初写在磁带的连续磁带单元格中。

机器从初始状态 q0 开始，磁头从左端标记“结束”开始扫描。在每个步骤中，它读取磁头下方磁带上的符号。它在该磁带单元格上写一个新符号，然后将磁头向左或向右移动一个磁带单元格。转换函数决定要采取的操作。

它有两个称为 accept state 和 reject state 的特殊状态。如果在任何时间点进入接受状态，则接受输入；如果进入拒绝状态，则 TM 拒绝输入。在某些情况下，它会继续无限运行，而不会被某些特定输入符号接受或拒绝。

Note - 带有半无限磁带的图灵机与标准图灵机等效。