2
$\begingroup$

I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows:

There are two different definitions of a time-constructible function. In the first definition, a function $f$ is called time-constructible if there exists a positive integer $n_0$ and Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps for all $n \ge n_0$. In the second definition, a function $f$ is called time-constructible if there exists a Turing machine $M$ which, given a string $1^n$, outputs the binary representation of $f(n)$ in $\mathcal{O}(f(n))$ time (a unary representation may be used instead, since the two can be interconverted in $\mathcal{O}(f(n))$ time).1

  1. If I am not mistaken the two definitions are not equivalent: The first one is more strict.
  2. I think this definitions are lacking the requirement that $f(n) \ge n$, since the part about converting an unary to a binary representation might not be true as this requires $f(n) \ge n$, i.e. the algorithm needs to be able to read the input, which might not be the case for small enough $f(n)$.

Am I right with this or am I missing something here?

$\endgroup$
1
  • 1
    $\begingroup$ (It was long ago, so I'm not confident) I think that you are right about 1, but it doesn't matter in applications (s.t. hierarchy theorems). 2 implies that $f(n) = o(n)$ is not time-constructible. $\endgroup$
    – Dmitry
    Commented Nov 5, 2021 at 10:52

0

Your Answer

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

Browse other questions tagged or ask your own question.