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?

  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Sep 13 '12 at 12:38
  • $\begingroup$ @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? $\endgroup$ – mrk Sep 13 '12 at 12:46
  • 2
    $\begingroup$ 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. $\endgroup$ – 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)$

  • $\begingroup$ Clear, but one question. Do the symbols in $\Sigma'$ have length $=1$? That's bugging me. $\endgroup$ – mrk Sep 16 '12 at 20:08
  • $\begingroup$ @saadtaame, yes all the $u_{i}$s are single symbols, there's just $\Sigma^{m}$ of them. $\endgroup$ – Luke Mathieson Dec 1 '12 at 0:18
  • $\begingroup$ @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? $\endgroup$ – mrk Dec 12 '13 at 22:33
  • $\begingroup$ @saadtaame: no, if the heads can move independently (in different directions), then the name of the model is multitape Turing machine, not multitrack Turing machine as in your question (and in my answer :) $\endgroup$ – Vor Dec 13 '13 at 9:09
  • $\begingroup$ I imagine that the simulation is much harder then. $\endgroup$ – mrk Dec 13 '13 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.