# Decidable non time constructible function

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$.

Thanks!

• 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. – Doralisa Feb 13 '15 at 19:44
• 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! – Ariel Feb 14 '15 at 0:14