Ace Test Series: Theory Of Computation - Turing Machine

Question

When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?

Answer 1

OPTION A) Take language a^nb^n now make single tape turing machine of it you will find that Time to accept this language is o(n^2)=T(n).

For the same language with multi-tape, store equal numbers of a and b in different tape here machine accept the language in o(n) time.

One must note that having a multi-ptape does not increase the power of TM,it can reduce the time to accept some language like in above case

Answer 2

The answer should be option “d” as it will take polynomial time ie O(n^2). Its not equal to option A.