Automata Theory 简明教程

Multi-track Turing Machine

多轨图灵机是多磁带图灵机的特定类型，它包含多个磁道，但只有一个磁头可以读取和写入所有磁道。在此，单个磁头可以一步从 n 个磁道中读取 n 个符号。它接受递归可枚举语言，就像普通单轨单带图灵机所接受的一样。

Multi-track Turing machines, a specific type of Multi-tape Turing machine, contain multiple tracks but just one tape head reads and writes on all tracks. Here, a single tape head reads n symbols from n tracks at one step. It accepts recursively enumerable languages like a normal single-track single-tape Turing Machine accepts.

多轨图灵机可以正式描述为一个 6 元组 (Q, X, ∑, δ, q0, F)，其中 −

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

  1. Q is a finite set of states

  2. X is the tape alphabet

  3. ∑ is the input alphabet

  4. δ is a relation on states and symbols where δ(Qi, [a1, a2, a3,…​.]) = (Qj, [b1, b2, b3,…​.], Left_shift or Right_shift)

  5. q0 is the initial state

  6. F is the set of final states

Note − 对于每一个单轨图灵机 S ，都有一个等价的多轨图灵机 M ，使得 L(S) = L(M) 。

Note − For every single-track Turing Machine S, there is an equivalent multi-track Turing Machine M such that L(S) = L(M).