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 ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.