Automata Theory 简明教程

Semi-Infinite Tape Turing Machine

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

A Turing Machine with a semi-infinite tape has a left end but no right end. The left end is limited with an end marker.

semi infinite tape

它是一条两轨磁带 -

It is a two-track tape −

  1. Upper track − It represents the cells to the right of the initial head position.

  2. Lower track − It represents the cells to the left of the initial head position in reverse order.

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

The infinite length input string is initially written on the tape in contiguous tape cells.

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

The machine starts from the initial state q0 and the head scans from the left end marker ‘End’. In each step, it reads the symbol on the tape under its head. It writes a new symbol on that tape cell and then it moves the head either into left or right one tape cell. A transition function determines the actions to be taken.

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

It has two special states called accept state and reject state. If at any point of time it enters into the accepted state, the input is accepted and if it enters into the reject state, the input is rejected by the TM. In some cases, it continues to run infinitely without being accepted or rejected for some certain input symbols.

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

Note − Turing machines with semi-infinite tape are equivalent to standard Turing machines.