Definition:Multitape Turing Machine
Definition
A multitape Turing machine is a generalization of the standard Turing machine.
Instead manipulating a single tape of symbols, the machine may have any finite number thereof, each with its own read-write head.
The machine chooses its moves for each tape based on the symbols read by every tape.
Formal Definition
Let $k \in \N_{\mathop > 0}$ be a positive natural number.
A $k$-tape Turing machine is a 7-tuple $\paren {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ that satisfies the following:
- $Q$ is a finite set, the states of the machine.
- $\Sigma$ is a finite set, the input symbols.
- $\Gamma \supsetneq \Sigma$ is a finite superset of the input symbols, called the tape symbols.
- For convenience, we also require that $\Gamma$ and $Q$ are disjoint.
- $\delta : Q \times \Gamma^k \to Q \times \Gamma^k \times \set {L, R, S}^k$ is a partial mapping, the transition function.
- $L$, $R$, and $S$ are arbitrary constants called directions.
- $q_0 \in Q$ is a distinguished state called the start state.
- $B \in \Gamma$ is a distinguished tape symbol called the blank symbol. $B$ must not be an element of $\Sigma$.
- $F \subset Q$ be a designated subset of the states called accepting states.
An instantaneous description of a Turing machine is a $k$-tuple of finite sequences of elements of $\Gamma \cup Q$, subject to the following conditions:
- There is a $q \in Q$ which appears exactly once in each sequence, and no other elements of $Q$ appear in any sequence
- The first entry in every sequence is not $B$.
- The last entry in every sequence is not $q$.
- If the last entry in the sequence is $B$, then the second-to-last is $q$.
By this definition, an instantaneous description can always be written as:
- $\tuple {X_{1,m_1} \dotsm X_{1,1} q Y_1 Z_{1,1} \dotsm Z_{1,n_1}; \dotsc; X_{k,m_k} \dotsm X_{k,1} q Y_k Z_{k,1} \dotsm Z_{k,n_k} }$
where the $m_p$ or $n_p$ may be $0$; $X_{p,i}$, $Y_p$, and $Z_{p,j}$ are all elements of $\Gamma$; and $q$ is an element of $Q$.
Additionally, $X_{p,m_p}$ and $Z_{p,n_p}$ are not $B$ if they exist; that is, if $m_p$ and $n_p$ are not $0$, respectively.
A move reduces one instantaneous description into another by applying the transition function.
We write $A \vdash B$ if a machine with instantaneous description $A$ has, after a single move, instantaneous description $B$.
Let $q$ be the shared element of $Q$ in $A$, and for each $1 \le p \le k$, let $Y_p$ be the entry of the $p$-th sequence that appears immediately after $q$.
- As $q$ is not the last entry in any sequence, there is always an entry immediately after it.
Let $\map \delta {q, Y_1, \dotsc, Y_k} = \paren{q', Y'_1, \dotsc, Y'_k, d_1, \dotsc, d_k}$.
Then, for each sequence $T_p$, there are eight cases to consider for the corresponding $T'_p$ in the next instantaneous description.
By abuse of notation, we will use $T_p \vdash T'_p$ to indicate this.
- If $d_p = L$ and $m_p > 0$, and either $n_p > 0$ or $Y'_p \neq B$ then:
- $X_{p,m} \dotsm X_{p,2} X_{p,1} q Y_p Z_{p,1} \dotsm Z_{p,n} \vdash X_{p,m} \dotsm X_{p,2} q' X_{p,1} Y'_p Z_{p,1} \dotsm Z_{p,n}$
- If $d_p = L$ and $m_p > 0$, but $n_p = 0$ and $Y'_p = B$ then:
- $X_{p,m} \dotsm X_{p,2} X_{p,1} q Y \vdash X_{p,m} \dotsm X_{p,2} q' X_{p,1}$
- If $d_p = L$ but $m_p = 0$, and either $n_p > 0$ or $Y'_p \neq B$ then:
- $q Y_p Z_{p,1} \dotsm Z_{p,n} \vdash q' B Y'_p Z_{p,1} \dotsm Z_{p,n}$
- If $d_p = R$ and $n_p > 0$, and either $m_p > 0$ or $Y'_p \neq B$ then:
- $X_{p,m} \dotsm X_{p,1} q Y_p Z_{p,1} Z_{p,2} \dotsm Z_{p,n} \vdash X_{p,m} \dotsm X_{p,1} Y'_p q' Z_{p,1} Z_{p,2} \dotsm Z_{p,n}$
- If $d_p = R$ and $n_p > 0$, but $m_p = 0$ and $Y'_p = B$ then:
- $q Y_p Z_{p,1} Z_{p,2} \dotsm Z_{p,n} \vdash q' Z_{p,1} Z_{p,2} \dotsm Z_{p,n}$
- If $d_p = R$ but $n_p = 0$, and either $m_p > 0$ or $Y'_p \neq B$ then:
- $X_{p,m} \dotsm X_{p,1} q Y_p \vdash X_{p,m} \dotsm X_{p,1} Y'_p q' B$
- If $m_p = 0$, $n_p = 0$, $Y'_p = B$, and $d_p$ is $L$ or $R$:
- $q Y \vdash q' B$
- If $d_p = N$:
- $X_{p,m} \dotsm X_{p,1} q Y_p Z_{p,1} \dotsm Z_{p,n} \vdash X_{p,m} \dotsm X_{p,1} q' Y'_p Z_{p,1} \dotsm Z_{p,n}$
Then, the following are exactly the valid moves:
- $A = \tuple {T_1; \dotsc; T_k} \vdash \tuple {T'_1; \dotsc; T'_k} = B$
Let $A \vdash^* B$ indicate that there exists a finite sequence $\sequence {A_i}_{0 \leq i \leq n}$ such that:
- $A = A_0 \vdash A_1 \vdash A_2 \vdash \dotso \vdash A_n = B$
The language $\map L M$ accepted by the machine $M$ is the set of strings $w \in \Sigma^*$ for which, for some $\sequence {\alpha_p}, \sequence {\beta_p} \in \paren {\Gamma^*}^k$ and $q_f \in F$:
- $\tuple {q_0 w; q_0 B; \dotsc; q_0 B} \vdash^* \tuple {\alpha_1 q_f \beta_1; \dotsc; \alpha_k q_f \beta_k}$
As a special case, the null string is in the language if and only if the above holds for $w = B$.
A machine $M$ halts on an input $w$, using the same special case for the null string as above, if and only if for some $\sequence {\alpha_p}, \sequence {\beta_p} \in \paren {\Gamma^*}^k$, $\sequence {X_p} \in \Gamma^k$, and $q \in Q$:
- $\tuple {q_0 w, q_0 B; \dotsc; q_0 B} \vdash^* \tuple {\alpha_1 q X_1 \beta_1; \dotsc; \alpha_k q X_k \beta_k}$
where $\map \delta {q, X_1, \dotsc, X_k}$ is undefined.