This is a more precise version of that question.

Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$.

**Update** Let us assume, as Joel suggested below that $M$ terminates on every input. The simplest thing to assume is that if $u\in L$, the TM eventually gives "yes" and if $u\not\in L$, it gives "no".

The smallest time (number of steps) of such a computation is denoted by $T_M(u)$. For every $n\ge 1$ we define $T_M(n)$ the maximum of all $T_M(u)$ for all accepted $u$ of length $\le n$. Then $T_M(n)\colon \mathbb{N}\to \mathbb{N}$ is the time function of $M$. If $M$ is a deterministic Turing machine, then its time function $T(n)$ is constructible that is there is a deterministic Turing machine which computes values $T(n)$ in time $\sim T(n)$.

**Question** Let $T(n)$ be the time function of a non-deterministic TM. Is it constructible? Is it {\it polynomally time constructible} that is there is a deterministic TM computing $T(n)$ in time $\sim T(n)^d$ for some $d\ge 1$?

I expect the answer to be "no" in both cases. Is it known?

6more comments