I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE turing machine using SINGLE-TAPE turing machine as follows.
Before the simulation the MULTI-TAPE turing machine is defined as follows:
A multitape TM is as suggested by Figure below. The device has a finite control (state), and some finite number of tapes. Each tape is divided into cells, and each cell can hold any symbol of the finite tape alphabet. As in the single-tape TM, the set of tape symbols includes a blank, and has a subset called the input symbols, of which the blank is not a member. The set of states includes an initial state and some accepting states. Initially:
The input, a finite sequence of input symbols, is placed on the first tape.
All other cells of all the tapes hold the blank.
The finite control is in the initial state.
The head of the first tape is at the left end of the input.
All other tape heads are at some arbitrary cell. Since tapes other than the first tape are completely blank, it does not matter where the head is placed initially all cells of these tapes "look" the same.
Fig.1: A multitape TM
Now the simulation is as follows:
$Theorem$ $1$: Every language accepted by a multitape TM is recursively enumerable.
PROOF: The proof is suggested by $Fig.2$. Suppose language $L$ is accepted by a $k$-tape TM $M$ . We simulate $M$ with a one-tape TM $N$ whose tape we think of as having $2k$ tracks. Half these tracks hold the tapes of $M$ , and the other half of the tracks each hold only a single marker that indicates where the head for the corresponding tape of $M$ is currently located. We assume $k = 2$. The second and fourth tracks hold the contents of the first and second tapes of $M$ , track $1$ holds the position of the head of tape $1$, and track $3$ holds the position of the second tape head.
Fig.2: SIMULATION OF MULTI-TAPE TURING MACHINE USING SINGLE TAPE TURING MACHINE
To simulate a move of $M$ , $N$ 's head must visit the $k$ head markers. So that $N$ not get lost, it must remember how many head markers are to its left at all times that count is stored as a component of N 's finite control. After visiting each head marker and storing the scanned symbol in a component of its finite control, $N$ knows what tape symbols are being scanned by each of $M$ 's heads. $N$ also knows the state of $M$ , which it stores in $N$ 's own finite control. Thus, $N$ knows what move $M$ will make.
$N$ now revisits each of the head markers on its tape, changes the symbol in the track representing the corresponding tapes of $M$ , and moves the head markers left or right, if necessary. Finally, $N$ changes the state of $M$ as recorded in its own finite control. At this point, $N$ has simulated one move of $M$ .
We select as $N$ 's accepting states all those states that record $M$ 's state as one of the accepting states of $M$ . Thus, whenever the simulated $M$ accepts, $N$ also accepts, and $N$ does not accept otherwise.▄
My query is : In the first line of the last paragraph of $Theorem$ $1$ what does the author mean by-
We select as N's accepting states all those states that record M's state as one of the accepting states of M. I feel that it means -all those states of $N$ are marked as accepting states which simulates one of the many accepting states of $M$. I don't know, may be I am wrong, please correct if I am.
Then the author moves on to say,
Why one cannot store tape-head positions as integers in the finite control?
He says:
One could argue that after n moves, the TM can have tape head positions that must be within n positions of original head positions, and so the head only has to store integers up to n. The problem is that, while the positions are finite at any time, the complete set of positions possible at any time is infinite.
My query is as follows : When the author considers the question,Why one cannot store tape-head positions as integers in the finite control? He justifies it by saying that The problem is that, while the positions are finite at any time, the complete set of positions possible at any time is infinite. Now the position number is finite. Now as per me, number of moves is also finite,so on adding or subtracting a finite number(due to the moves) to the position, we get a finite number as position. But is it so that the infiniteness described above is due to the fact that we do not possibly know the maximum number of finite moves exactly.
The author then derives the time-complexity of operation of the simulation as:
$Theorem$ $2$: The time taken by the one-tape TM $N$ of previous theorem to simulate $n$ moves of the $k$-tape TM $M$ is $O(n^{2})$.
PROOF: After $n$ moves of $M$ , the tape head markers cannot have separated by more than $2n$ cells. Thus, if $N$ starts at the leftmost marker, it has to move no more than $2n$ cells right, to find all the head markers. It can then make an excursion leftward, changing the contents of the simulated tapes of $M$ , and moving head markers left or right as needed. Doing so requires no more than $2n$ moves left, plus at most $2k$ moves to reverse direction and write a marker $X$ in the cell to the right (in the case that a tape head of $M$ moves right). Thus, the number of moves by $N$ needed to simulate one of the first $n$ moves is no more than $4n + 2k$. Since $k$ is a constant, independent of the number of moves simulated, this number of moves is $O(n)$. To simulate $n$ moves requires no more than $n$ times this amount, or $O(n^{2})$.▄
Now my query is when the author is considering the derivation of the time complexity of the simulation he says that after $n$ moves of the MULTI-TAPE turing machine, the relative position of the head markers in the simulation is at most $2n$ (i.e. worst case). Now the tape-head markers are arbitrary distance apart before any move of the multi-tape TM. Let the distance be $d$. So after the said $n$ moves of the multi-tape turing machine, the left head marker can go at most $n$ cells left and the right head marker can go at most $n$ cells right. So the relative worst case distance is $2n+d$. Now in each move the relative distance is obviously upper bounded by the term $2n+d$ and then we do the later calculation. The way I am thinking I am getting an extra term $d$ , which is not considered by the author.
