4
$\begingroup$

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?

$\endgroup$
3
  • 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
    Commented Sep 13, 2012 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
    Commented Sep 13, 2012 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
    Commented Sep 13, 2012 at 13:23

1 Answer 1

4
$\begingroup$

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)$

$\endgroup$
6
  • $\begingroup$ Clear, but one question. Do the symbols in $\Sigma'$ have length $=1$? That's bugging me. $\endgroup$
    – mrk
    Commented Sep 16, 2012 at 20:08
  • $\begingroup$ @saadtaame, yes all the $u_{i}$s are single symbols, there's just $\Sigma^{m}$ of them. $\endgroup$ Commented Dec 1, 2012 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
    Commented Dec 12, 2013 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
    Commented Dec 13, 2013 at 9:09
  • $\begingroup$ I imagine that the simulation is much harder then. $\endgroup$
    – mrk
    Commented Dec 13, 2013 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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