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