Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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