2
$\begingroup$

I am reading [1]. In [1], Claim 1.5 and its proof sketch are as follows:

Claim 1.5 For every $f: \{0, 1\}^* \rightarrow \{0, 1\}$ and time-constructible $T: \mathbb{N} \rightarrow \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using alphabet $\Gamma$, then it is computable in time $4 \log |\Gamma| T(n)$ by a TM $\tilde{M}$ using the alphabet $\{0, 1, \square, \rhd\}$. $\diamond$

Proof Sketch: Let $M$ be a TM with alphabet $\Gamma$, $k$ tapes, and state set $Q$ that computes the function $f$ in $T(n)$ time. We describe an equivalent TM $\tilde{M}$ computing $f$ with alphabet $\{0, 1, \square, \rhd\}$, $k$ tapes and a set $Q'$ of states. The idea behind the transformation is simple: One can encode any member of $\Gamma$ using $\log |\Gamma|$ bits. (Recall our convention that $\log$ is taken to base 2, and noninteger numbers are rounded up when necessary.) Thus, each of $\tilde{M}$'s work tapes will simply encode one of $M$'s tapes: For every cell in $M$'s tape we will have $\log|\Gamma|$ cells in the corresponding tape of $\tilde{M}$ (see Figure 1.3).

Figure 1.3 of [1]

To simulate one step of $M$, the machine $\tilde{M}$ will (1) use $\log|\Gamma|$ steps to read from each tape the $\log|\Gamma|$ bits encoding a symbol of $\Gamma$, (2) use its state register to store the symbols read, (3) use $M$'s transition function to compute the symbols $M$ writes and $M$'s new state given this information, (4) store this information in its state register, and (5) use $\log|\Gamma|$ steps to write the encodings of these symbols on its tapes.

One can verify that this can be carried out if $\tilde{M}$ has access to registers that can store $M$'s state, $k$ symbols in $\Gamma$, and a counter from 1 to $\log|\Gamma|$. Thus, there is such a machine $\tilde{M}$ utilizing no more than $c |Q| |\Gamma|^{k+1}$ states for some absolute constant $c$. (In general, we can always simulate several registers using one register with a larger state space. For example, we can simulate three registers taking values in the sets $A$, $B$, and $C$, respectively, with one register taking a value in the set $A \times B \times C$, which is of size $|A| |B| |C|$.)

It is not hard to see that for every input $x \in \{ 0, 1\}^n$, if on input $x$ the TM $M$ outputs $f(x)$ within $T(n)$ steps, then $\tilde{M}$ will output the same value within less than $4 \log |\Gamma| T(n)$ steps. $\blacksquare$

My questions is: Why is the number of states of $\tilde{M}$ no more than $c |Q| |\Gamma|^{k+1}$? Any comments and answers are welcome. Thanks in advance.

Reference

[1] S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

In the suggested sketch, the machine $\widetilde{M}$, upon simulating a step of $M$, needs to remember, in its state-space, the following information:

  • The current state of $M$ -- there are $|Q|$ possible states.
  • The $k$ read letters -- there are $|\Gamma|^k$ possibilities.
  • A counter whose value is at most $log(|\Gamma|)$.

Proceed from here.

Improve this answer
$\endgroup$
5
  • $\begingroup$ To Bader Abu Radi: Thank you very much for your answer. I will read and try to understand your answer. $\endgroup$
    – Wei-Cheng Liu
    Commented Aug 12 at 2:19
  • $\begingroup$ To Bader Abu Radi: If I understand correctly, then the number of states of the machine $\tilde{M}$ should be exactly $|Q| |\Gamma|^k \log(|\Gamma|)$. Why does Arora and Barak write that the number of states of $\tilde{M}$ is no more than $c |Q| |\Gamma|^{k+1}$? $\endgroup$
    – Wei-Cheng Liu
    Commented Aug 12 at 2:47
  • $\begingroup$ There is a grammatical error in the above comment. "Why does" should be "Why do". $\endgroup$
    – Wei-Cheng Liu
    Commented Aug 12 at 3:15
  • 1
    $\begingroup$ First, note that $log(|\Gamma|) \leq |\Gamma|$, so it is easy to bound the expression as the authors did. However, the real reason for that, I guess, is that in these high-level proofs, it is hard to nail down the exact number of states, so we estimate an upper bound that asymptotically is as good, and they did that nicely. You can tell well, but I use more 20 states to remember that I am doing this and that, but it doesn't matter as it is still bounded by $|Q||\Gamma|^{k+1}$ up to a constant. So the state space grows polynomial in $Q$ and $\Gamma$, yet exponentially in $k$. $\endgroup$
    – Bader Abu Radi
    Commented Aug 12 at 10:30
  • $\begingroup$ OK, I understand. Thank you very much. $\endgroup$
    – Wei-Cheng Liu
    Commented Aug 13 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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