Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. Moreover, the Turing machine has $27$ states.

I wonder how come the running time of such machine is $O(n^{1+\log_2 2006}\cdot \log_2n)$ (The answer is the correct choice for this multiple choices question out of an exam I practise)

  • $\begingroup$ I dont get this question. What is Aleph Bet signs? Please formulate proper sentences. $\endgroup$ – A.Schulz Dec 14 '12 at 19:20

This bound comes from the number of possible configurations. If you do more steps than you have configurations, you are in a cycle.

So let us quickly get a bound for the number of configurations. You have $100+\log n$ possible positions for the head on the work tape and $n$ positions for the head on the input tape. The work tape can contain $2006^{100+\log n}$ different words. Furthermore there are 27 states. Combining everything gives $$ \begin{align} 27n \cdot (100+\log n) \cdot 2006^{100+\log n}&=27\cdot2006^{100}(100n+n\log n) n^{\log 2006}\\ &=O((100n+ n\log n) n^{\log 2006})\\ &=O(\log n\cdot n^{1+\log 2006})\\ \end{align}$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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