# How does a single-track Turing machine simulate a multi-track Turing machine?

It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification of a transition function that does the job. If there are $k$ tracks, then we can think of symbols as being vectors and arrange them one after another in the tape; but again, what's the transition function like in the equivalent single-track machine?

• This is a fairly standard exercise. What are your specific problems with the transition function? (I seem to remember that there are some related questions around, discussion the performance impact of such a simulation.) – Raphael Sep 13 '12 at 12:38
• @Raphael If $\delta_k(q, [x_1,\dots,x_k]) = [y_1,\dots,y_k]$ where $\delta_k$ is the multi-track transition function, how is $\delta$, the single-track transition function, defined as to guarantee equivalence? – mrk Sep 13 '12 at 12:46
• I think you need a more general idea before looking at individual transitions. You may need to do some additional bookkeeping/tape management not easily seen/expressed in single transitions. – Raphael Sep 13 '12 at 13:23

If $\Sigma = (x_1,...,x_n)$ is the alphabet of the $m$-tracks $TM$, just use an expanded alphabet $\Sigma' = \Sigma \times ... \times \Sigma$ for the single-track $TM'$ ($|\Sigma'| = n^m$).
Every vector $\bar{x}_i$ of $m$ symbols from $\Sigma$ can be mapped to a unique alphabet symbol $u_i$ in $\Sigma'$: $\bar{x}_i = (x_{i_1},x_{i_2},...,x_{i_m}) \rightarrow u_i \in \Sigma'$
Hence every transition of $TM$ $(q_h,(x_{i_1},x_{i_2},...,x_{i_m}))\rightarrow (q_k,(x_{j_1},x_{j_2},...,x_{j_m}),dir)$ can be mapped to an equivalent transition in $TM'$ where the "read vector" $\bar{x_i}$ and "write vector" $\bar{x_j}$ are replaced with the corresponding alphabet symbols in $\Sigma'$: $(q_h,u_i)\rightarrow (q_k,u_j,dir)$
• Clear, but one question. Do the symbols in $\Sigma'$ have length $=1$? That's bugging me. – mrk Sep 16 '12 at 20:08
• @saadtaame, yes all the $u_{i}$s are single symbols, there's just $\Sigma^{m}$ of them. – Luke Mathieson Dec 1 '12 at 0:18
• @Vor I accepted this answer but now as I'm reading I have new questions. Why is there only one $dir$ in the transition function of the m-tracks TM? Isn't it that every track has a head that can move left, right, or not move at all? – mrk Dec 12 '13 at 22:33