In Fig. $8.17$ we saw an example of the general simulation of a $k$-tape $TM$ by a one-tape $TM.$
- Suppose this technique is used to simulate a $5$-tape $TM$ that had a tape alphabet of seven symbols. How many tape symbols would the one-tape $TM$ have?
- An alternative way to simulate $k$ tapes by one is to use a $(k+1)$st track, to hold the head positions of all $k$ tapes, while the first $k$ tracks simulate the $k$ tapes in the obvious manner. Note that in the $(k+1)$st track, we must be careful to distinguish among the tape heads and to allow for the possibility that two or more heads are at the same cell. Does this method reduce the number of tape sysmbols needed for the one-tape $TM$?
- Another way to simulate $k$ tapes by $1$ is to avoid storing the head positions altogether. Rather, a (k+1)st track is used only to mark one cell of the tape. At all times, each simulated tape is positioned on its track so the head is at the marked cell. If the $k$ tape $TM$ moves the head of tape $i$, then the simulating one-tape $TM$ slides the entire nonblank contents of the $i^{th}$ track one cell in the opposite direction, so the marked cell continues to hold the cell scanned by the $i^{th}$ tape head of the $k$-tape $TM$. Does this method help reduce the number of tape symbols of the one-tape $TM$? Does it have any drawbacks compared with the other methods discussed?
