1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – Yuval Filmus
    Feb 13, 2021 at 8:49

0

Reset to default

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.