I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof:

For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f is computable in time T(n) by a TM M using alphabet A, then it is computable in time 4log|A|T(n)by a TM M ̃ using the alphabet {0,1,Blank,◃}.

The proof is on the link :

First Part of proof

Second Part

So basically if we have a running time of T(n) on a certain alphabet A and we wanna switch to binary.. we gonna have to multiply it by log(|A|) (log of base 2, the number of bits to represent an element from A) because every step will be multiplied by the number of bits used to represent the element.

But in the proof, starting from the second paragraph, i dont really understand what they say and how they end up with the '4' in '4log|A|T(n)'.


The first part the proof reads "To simulate one step of $M$, the machine $M^{\sim}$ will: (1) ... (2)... (3)... (4) and (5) ....". Can you see the factor of 4?

You have a good understanding regarding the factor $\log|A|$. Let us take a close look at the steps in each stage of $M^{\sim}$ above. There are $\log|A|$ steps in stage (1) and in stage (5). However, there is only one step in stage (2) or stage (3) or stage (4). So there are less than $2\log|A|$ steps in stage (2), (3) and (4) combined, assuming $\log|A|\gt1$. If $\log|A|=1$, we can just let $M^\sim$ be $M$ and we are done. So there are less than $\log|A|+\log|A|+2\log|A|=4\log|A|$ steps of $M^\sim$ for one step of $M$.

The second part of the proof is justifying that the stage (2), (3) or (4) can be done in one step of machine $M^{\sim}$. It explains the power of larger registers. It points out that we can use more states in $M^\sim$ to identify the possibly much more situations ("states" could have been a better word had we not reserved that word for Turing machine) of the machine. Take your time. You will understand.

  • 1
    $\begingroup$ and cuz we will do all of these steps in every step of M, we will end up with that complexity ... Got it now, Thank you so much. $\endgroup$ Jun 13 '19 at 13:03

To simulate one step for M,M~

  1. There are log|A| steps in stage (1) . (log|A| steps)
  2. in stage (5),the heads want to write log|A| bits,the heads should use log|A| steps go back to the bagaining position,then use log|A| steps to write log|A| bits.(2log|A| steps)
  3. the head should move to next symbol,just 1 stps needed(1<=log|A|)

we find that M~ should use less than 4log|A| steps to simulate one step for M,so M~ less than 4log|A|T(n) steps.

  • $\begingroup$ (2) and (3) and (4) are not a step of M or M~. $\endgroup$
    – zxpdog
    Jun 24 at 13:14

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.