In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th shift can cost just $O(2^k)$ time. One can read the proof for complete details but I can explain my doubt as the following problem.

Assume a TM tape divided into blocks where for $i \geq 0$ the $i$th block contains $2^i$ cells. Further, assume that the $k$th block is full i.e. all $2^k$ cells in that block have some symbol of the alphabet and for all $0 \leq i < k$, the $i$th block is empty i.e. they have no symbols. Now, we need to take first $2^{k-1}$ symbols present in $k$th block and put the left most in first block, then start putting rest of the symbols in sequence by filling first half of every $i$th block for $i < k$. One can check that we have exactly that many symbols to place in lower indices block's first half.

The book say that it can be done in $O(2^k)$ time, which I am not able to prove.


Your Answer

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

Browse other questions tagged or ask your own question.