# Time functions of non-deterministic Turing machines

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$. The smallest time of such a computation is denoted $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$.

Question. Can one characterize all time functions of non-deterministic Turing machines, say, in terms of the time complexity of computing their values?

Update Time functions of deterministic Turing machines are time-constructible. Since there is an exponential slowdiown when going from non-deterministic to deterministic TM, there is a similar restriction for non-deterministic time function. The question is: what is the "correct" restriction.

• I guess this question is most interesting when $L$ is recognizable, but it's complement is not (so $L$ is not computable). In this case $T_M(n)$ will not have a computable upper bound. In this case, the choice of non-deterministic versus deterministic Turing machines doesn't matter so much, since it's just an exponential slowdown to move from non-deterministic to deterministic Turing machines, which is nothing compared to the growth rate of $T_M(n)$. However, we should be able to get an upper-bound on the growth rate of $T_M(n)$: it must have an upper-bound computable in the halting set. – James Aug 1 '18 at 6:41
• @James: I do not need examples, I need a characterization of the class of functions. – Mark Sapir Aug 1 '18 at 7:24
• I need a characterization in the form: $f$ belongs to the class (at least asymptotically) iff there exits a Turing machine computing the values $f(n)$ in time ... The most interesting functions in that class - all. – Mark Sapir Aug 1 '18 at 8:03
• I'm also a little bit confused, but can you perhaps explain in more detail exactly what kind of result you're expecting? In particular, it's certainly the case that essentially all computable $f()$ (at least those with $f(n)\geq n$) are in the class, which seems to make any questions about the time needed to compute $f()$ largely moot? – Steven Stadnicki Aug 3 '18 at 4:21
• @StevenStadnicki: It is not true that essentially all computable functions are in the class. The time function $T(n)$ is computable in time at most $T(n)$ non-deterministically: run the TM and a counting TM in parallel (the second TM counts the steps of the first TM). – Mark Sapir Aug 3 '18 at 10:20