半无限带图灵机
具有半无限磁带的图灵机有左端但没有右端。左端由末端标记限制。
这是一个双轨磁带 -
上轨道- 它代表初始头部位置右侧的单元格。
Lower track - 它以相反的顺序表示初始头部位置左侧的单元格。
无限长度的输入字符串最初写入磁带上的连续磁带单元中。
机器从初始状态q 0开始，头从左端标记“End”开始扫描。在每一步中，它都会读取头下磁带上的符号。它在该磁带单元上写入一个新符号，然后将磁头移动到左侧或右侧的一个磁带单元中。转换函数决定要采取的操作。
它有两个特殊的状态，称为接受状态和拒绝状态。如果在任何时间点进入接受状态，则输入被接受；如果进入拒绝状态，则输入被TM拒绝。在某些情况下，它会继续无限运行，而不会接受或拒绝某些特定的输入符号。
注- 具有半无限磁带的图灵机相当于标准图灵机。