Equivalence from multi-tape to single-tape implies limited write space?

Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:

$ A$ : “adds a $ at the beginning of the tape.”

So we have: $ $ \begin{array}{lc} \text{Before }: & 0101\sqcup\sqcup\sqcup\ldots\ \text{After }A: & $ 0101\sqcup\sqcup\ldots \end{array} $ $

And it is running on a multi-tape turing machine. The equivalence theorem from Sipser book proposes we can describe any multi-tape TM with a single-tape applying the following “algorithm”, append a $ \#$ at every tape and then concat every tape in a single tape, and then put a dot to simulate the header of the previous machine, etc, etc.

With $ a$ and $ b$ being the content of other tapes, we have: $ $ a\#\dot{0}101\#b $ $ If we want to apply $ A$ or another subroutine that uses more space, the “algorithm” described in Sipser is not enough, I can intuitively shift $ \#b$ to the right, but how to describe it more formally for any other subroutine that uses more space in the tape? I can’t figure out a more general “algorithm” to apply in this cases.

Simulating multi-tape turing machines by single-tape TM

In “Computational Complexity: A modern approach”, Arora and Barak proof the following Claim:

Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, work, and output tape. For every $ f: \{0,1\}^* \rightarrow \{0,1\}$ and time-constructible $ T: \mathbb{N} \rightarrow \mathbb{N}$ , if $ f$ is computable in time $ T(n)$ by a TM $ M$ using $ k$ tapes, then it is computable in time $ 5kT(n)^2$ by a single-tape TM $ \hat{M}$ .

The proof roughly goes like this, from my understanding:

-> We encode the $ k$ tapes of $ M$ on a single tape, using locations $ i,k+i,2k+i$ for the $ k$ -th tape.

-> For each character $ a$ in M’s alphabet, we define another character $ \hat{a}$ in $ \hat{M}$ ‘s alphabet. For each of M’s tapes, the $ \hat{a}$ character indicates the current position of that respective tape (for $ M$ ) in $ M’s$ encoding.

-> For each state transition of $ M$ , $ \hat{M}$ then perform two sweeps: One left-to-right, where $ \hat{M}$ finds the positions of $ M$ at the respective working tapes and one right-to-left where $ \hat{M}$ updates its tape encoding according to state transition function of $ M$ .

Its not clear to me how the first step exactly works. Arora and Barak write: “First it sweeps the tape in the left-to-right direction and records to its register the $ k$ symbols that are marked by $ \hat{a}$ “. As far as I understand, registers correspond to states in the TM $ M’$ . What is exactly is meant by recording the symbols to its register?

Difference between multi-tape Turing machine and single tape machine

A beginner’s question about “fine-grained” computational power.
Let $ M_k$ be a $ k$ -tapes turing machine, and let $ M$ be a single tape turing machine. We know that $ M_k$ and $ M$ both have the same “computable power”. In addition, one can simulate $ M_k$ on $ M$ in a way that every computation which takes $ O(t(n))$ on $ M_k$ will take $ O(t(n) \log(t(n))$ on $ M$ .
Here is my question:
Is there a language $ L$ such that $ L$ can be decided in $ O(n)$ time in $ k$ -tape Turing machine (for fixed $ k$ , say 2), but can’t be decided in $ O(n)$ time in a single tape machine? (every single tape machine which decides $ L$ needs $ \Omega(n \log n)$ time).
In addition, are there any examples of two computational models (classical, not the quantum model) with the same computable power, but with fine-grained differences in their running time? (I guess that major changes in running time would contradict the extended Church-Turing thesis, which is less likely).

Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register.

Suppose the time complexity of M is T(n):

- n : is the input length - T : the number of steps the Turing machine does :     - change the value of a symbol then move either left, right or stay in its place. 

So, suppose our input is in the following way :

| 1. | 0 | 1 | 1. | 0 | 1 | 1 | 1 | 1 | 0. | 0 |  

the dots represent where the tapes are ( in our case, we have 3 tapes)

So, for every step, we gonna do the following :

1- Sweep from left to right and copy all the dotted symbols in a register  2- Make the transition :     eg, if we have 101 in the register, we gonna use the transition to get the result :          delta(101) = 001 while delta is the transition function for M.          Then we gonna change the content of the register to 001. 3- Sweep from right to left and copy the value we had and change the dots places (tapes movement) 

The complexity of this process is going to be :

1- sweeping and copying gonna be done at most ’n’ times for every step of M.  2- make the transition  3- sweep again from left to right to put the changes and change the dots places which is going to be done at most ’n’ times 

We end up with :

n T(n) + T(n) + n T(n) = (2n + 1) T(n)  

Then if a k-tape Turing machine is capable of doing somehting in T(n) then a single-taped one can do it in (2n+1) T(n) ..

Im following for my studies on Turing machines and Complexity In general this book : “Computational Complexity: A Modern approach” after having done lot of search concerning this subject. And in this book here is the statement and proof they are giving :

proof1

proof2

I see that they used a different way of putting the tapes … but i guess we should get to the same result .. where did i mess it up ?

Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register.

Suppose the time complexity of M is T(n):

- n : is the input length - T : the number of steps the Turing machine does :     - change the value of a symbol then move either left, right or stay in its place. 

So, suppose our input is in the following way :

| 1. | 0 | 1 | 1. | 0 | 1 | 1 | 1 | 1 | 0. | 0 |  

the dots represent where the tapes are ( in our case, we have 3 tapes)

So, for every step, we gonna do the following :

1- Sweep from left to right and copy all the dotted symbols in a register  2- Make the transition :     eg, if we have 101 in the register, we gonna use the transition to get the result :          delta(101) = 001 while delta is the transition function for M.          Then we gonna change the content of the register to 001. 3- Sweep from right to left and copy the value we had and change the dots places (tapes movement) 

The complexity of this process is going to be :

1- sweeping and copying gonna be done at most ’n’ times for every step of M.  2- make the transition  3- sweep again from left to right to put the changes and change the dots places which is going to be done at most ’n’ times 

We end up with :

n T(n) + T(n) + n T(n) = (2n + 1) T(n)  

Then if a k-tape Turing machine is capable of doing somehting in T(n) then a single-taped one can do it in (2n+1) T(n) ..

Im following for my studies on Turing machines and Complexity In general this book : “Computational Complexity: A Modern approach” after having done lot of search concerning this subject. And in this book here is the statement and proof they are giving :

proof1

proof2

I see that they used a different way of putting the tapes … but i guess we should get to the same result .. where did i mess it up ?