## 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 :

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 :

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 ?