patternMinor
Speed-up of two-tape Turing machine
Viewed 0 times
twotapemachineturingspeed
Problem
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#7248, answer score: 3
Revisions (0)
No revisions yet.