I'm reading Computational Complexity by Arora and Barak and I had a doubt regarding a statement made about the equivalence of Turing machines:

For every $f\colon \{0, 1\}^∗ → \{0, 1\}$ and time-constructible $T\colon \mathbb N → \mathbb N$, if $f$ is computable in time $T (n)$ by a Turing machine $M$ using alphabet $\Gamma$ then it is computable in time $4\log|\Gamma|T (n)$ by a Turing machine $\tilde{M}$ using the alphabet $\{0, 1, \square, B\}$.

Specifically, what if any role $T$ being time constructible has here?

The proof (sketch) encodes $\Gamma$ in binary, and uses a larger register to simulate $M$'s transition function, and also a counter. But I don't think $T$ being time constructible comes into play. Could someone confirm or tell me if I'm missing something?

  • 1
    $\begingroup$ It doesn't seem to come into play. But since we never encounter non-time-constructible functions in practice, the difference doesn't really matter. $\endgroup$ Feb 13, 2021 at 8:49


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.