[Solved]: Speed-up of two-tape Turing machine

Problem Detail: 

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.

Asked By : com

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7248