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 ?