Problem Detail: Note: This is a part of a homework question Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n mid n geq 0$} Then it says “Discuss how much time your machines saves over a one-tape DTM using the same algorithm” Any hint? Here’s my algorithm: (1) Cut-and-paste c’s to tape 3 (2) Cut-and-paste b’s to tape 2 (3) Cross out each triplets, accept if last round cuts all three, reject if there’s leftover Which seems like it has a time complexity of $O(n+n+3n)=O(5n)$ Then how do we determine the time complexity for the one-tape version?
Asked By : Iancovici
Answered By : Iancovici
Figured it out. Turns out a theorem states that
For any multi-tape DTM $M$, there exists a two-way, one-tape DTM $M_1$ computing the same function s.t. for all inputs $x$, $Time_{M_1}(x) leq c centerdot (Time_M(x))^2$
Reference: Du, Dingzhu, and Ker Ko. Problem solving in automata, languages, and complexity. New York: Wiley, 2001. Print.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11053
