Automata Theory 简明教程

Multi-tape Turing Machine

多磁带图灵机有多个磁带,每个磁带都通过一个单独的磁头进行访问。每个磁头可以独立于其他磁头移动。最初输入在磁带 1 上,其他磁带为空。一开始,第一磁带被输入占据,其他磁带保持空白。接下来,机器读取其磁头下的连续符号,TM 在每个磁带上打印一个符号并移动其磁头。

Multi-tape Turing Machines have multiple tapes where each tape is accessed with a separate head. Each head can move independently of the other heads. Initially the input is on tape 1 and others are blank. At first, the first tape is occupied by the input and the other tapes are kept blank. Next, the machine reads consecutive symbols under its heads and the TM prints a symbol on each tape and moves its heads.

multi tape turing machine

多磁带图灵机可正式描述为 6 元组 (Q, X, B, δ, q0, F),其中 -

A Multi-tape Turing machine can be formally described as a 6-tuple (Q, X, B, δ, q0, F) where −

  1. Q is a finite set of states

  2. X is the tape alphabet

  3. B is the blank symbol

  4. δ is a relation on states and symbols where δ: Q × Xk → Q × (X × {Left_shift, Right_shift, No_shift })k where there is k number of tapes

  5. q0 is the initial state

  6. F is the set of final states

Note - 每个多磁带图灵机都有一个等效的单磁带图灵机。

Note − Every Multi-tape Turing machine has an equivalent single-tape Turing machine.