半无限带图灵机



带半无限带的图灵机有一端,但没有另一端。该端用结束标记限制。

Semi-infinite Tape

它是一个双轨带:

  • 上轨 - 它表示初始磁头位置右边的单元格。

  • 下轨 - 它表示初始磁头位置左边的单元格,顺序相反。

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

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

它有两个特殊状态,称为接受状态拒绝状态。如果在任何时候它进入接受状态,则接受输入;如果它进入拒绝状态,则图灵机拒绝输入。在某些情况下,对于某些特定的输入符号,它会无限期地运行而不会被接受或拒绝。

注意 - 带半无限带的图灵机等效于标准图灵机。

广告