Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ such that $M_f(x)=f(x)$, but is not time constructible, meaning that any machine $M_f$ deciding $f$ runs in time greater than $f$.


  • 2
    $\begingroup$ Here is a similar question:math.stackexchange.com/questions/55096/… and in wiki en.wikipedia.org/wiki/Constructible_function mentioned that No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. $\endgroup$ – Doralisa Feb 13 '15 at 19:44
  • $\begingroup$ ah excellent, i was looking for something to contradict the time hierarchy theorem but failed. The example of $f(n)=2n+A(n)$ where $A\in DTIME(n^2)\setminus DTIME(n)$ given in your first link is the sort of thing i was looking for. Thanks! $\endgroup$ – Ariel Feb 14 '15 at 0:14

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.