I try to figure out linear speed-up of Turing machine.

Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity $t′$, where $t′(n) = O(n) + (t(n)/2)$.

The idea seems to show that what the first machine does within two steps the second machine is capable to do within one step. Time complexity $O(n)$ seems to be complexity of encoding input of first machine to input of second machine.

I have a problem with proving this statement and will appreciate any help.

In addition, why only two-tape Turing machine was mentioned, what about one-tape Turing machine.


The single tape case is known as the Linear speedup theorem. It has a nice little trick by compressing the tape and using overlapping chunks of the tape. Try whether it also works in the two-tape case.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.