半无限磁带图灵机

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

它是双轨磁带 −

• 上轨 − 它代表初始头部位置右侧的单元。

• 下轨 −它以相反的顺序表示初始头部位置左侧的单元格。

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

机器从初始状态q₀开始，头部从左端标记"End"开始扫描。在每个步骤中，它都会读取头部下方磁带上的符号。它在该磁带单元格上写入一个新符号，然后将头部移动到左侧或右侧一个磁带单元格。转换函数确定要采取的操作。

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

注意 −具有半无限带的图灵机与标准图灵机等效。