So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?
I just don't know where to get started...
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Multi-tape Turing Machine running in $O(f(n))$ can be simulated by a single-tape Turing machine running in $O(f^2(n))$.
Try writing a single-tape Turing machine that stores symbols from your $3$ tapes on its one tape, separated by some unique symbol not in $\Sigma$.
hint: For every step of your $k$-tape machine, a one-tape machine must first do at most $k\cdot n$ steps to find the position.
answered Nov 17, 2018 at 15:31