The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language:

$\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\}$

It is said that $f$ is logspace computable if $\text{BIT}_f$ is decidable in space $O(\log n)$. Decidable means that there exist a Turing Machine $M$ such that:

  1. if $\langle x,i \rangle \in \text{BIT}_f$ then $M(\langle x,i \rangle) = 1$
  2. if $\langle x,i \rangle \notin \text{BIT}_f$ then $M(\langle x,i \rangle) = 0$

Prove that the composition $(f \circ g)(x)=f(g(x))$ of two logspace computable functions $f,g$ is also a logspace computable function.

Any hint on this exercise? What I tried so far is playing with the composition of the two Turing Machines associated with $f$ and $g$, but I didn't succeed because it always end up with a case analysis exercise.


1 Answer 1


The idea is quite simple. We are going to simulate running $M_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M_f$ attempts to read from the input tape, we invoke the machine computing $\mathrm{BIT}_g$, which also uses up $O(\log n)$ steps; we know which input $i$ to give, since this is just the location of the head.

  • $\begingroup$ And what happens when M_f needs to know the size of its input, which is |g(x)|? How can it obtain it by just invoking BIT_g? $\endgroup$ Commented Feb 26, 2020 at 12:27
  • $\begingroup$ How does $M_f$ get to know the size of its input usually? Presumably it scans its input until reaching a blank. You can do the same here (the definition of BIT is hiding this issue). $\endgroup$ Commented Feb 26, 2020 at 12:34
  • $\begingroup$ Well, this is the problem I see. When it scans the first bit of its input, which should be the "i" value used to invoke BIT_g? Or equivalently, how will it reach a blank if every time it reads from its virtual input tape, there will be a 0 or a 1, depending on the output of BIT_g? $\endgroup$ Commented Feb 26, 2020 at 12:38
  • $\begingroup$ The definition of BIT just doesn’t make sense, since it doesn’t state what happens if $i$ is out of bounds. Either the length is known ahead of time (answering your question), or you need three possible output values. In any case, this is just a technicality. $\endgroup$ Commented Feb 26, 2020 at 12:40
  • 1
    $\begingroup$ It’s a technicality which can be handled in many ways. You choose how. $\endgroup$ Commented Feb 26, 2020 at 12:57

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.