# Time functions of non-deterministic Turing machines (a better question)

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?

• wouldn't it make more sense to improve your previous question, by making it more precise, rather than ask a new one? Aug 5, 2018 at 19:19
• The previous version also makes sense. There may be different characterizations, not involving the notion of "constructible".
– user6976
Aug 5, 2018 at 19:23
• Could you clarify what constructible means for the case where no strings of that length or smaller are accepted? In this case, $T_M$ would seem to be a partial function. For example, perhaps all strings in the language have length at least $17$. In this case it would seem that $T_M(5)$ is either undefined or infinite, but I am less clear what you mean by constructible in this case. Aug 5, 2018 at 19:23
• @JoelDavidHamkins: The functions are usually considered asymptotically that is the first few values are ignored (or $n\gg 1$). Alternatively, we can assume that these values are $\infty$. Of course if the machine accepts the empty language, its time function is empty but that is not an interesting case.
– user6976
Aug 5, 2018 at 19:26
• You say $M$ is non-deterministic, but I guess you intend that there are no non-halting computations of $M$ on any input? This would be like the usual NP situation, where on any input pair $(u,w)$, where $W$ is a possible witnesses for $u$, you get a yes-or-no answer in some bounded time, whether that witness is good enough. Is this your context? If not, and if you just use non-deterministic machines as they are often described, then you can code the halting problem into your time function, and it might not be computable at all, let alone constructible. Aug 5, 2018 at 19:35

The way you have set up the question, the answer is negative, even for deterministic machines.

To see this, let $L$ be the halting problem, consisting of strings $u$ describing a Turing machine, which halts when started on an empty tape.

This language is recognized by a Turing machine $M$, which on input $u$ simply simulates the computation of that program on an empty tape, and accepts $u$ if this simulation halts. In other words, $u$ is in the language if and only if $u$ is accepted by some computation of $M$, which is what you requested.

For $u$ that are accepted, the time complexity $T_M(u)$ is at least as large as the length of the computation of $u$ on the empty tape, since the simulation takes at least as long as the real thing. Thus, $T_M(n)$ is at least as large as the busy beaver function, since the number of states of the machine coded by a string $u$ is at most the length of $u$. This function is therefore not computable at all, let alone constructible.

As I mentioned in my comment, however, one can avoid this kind of example if you insist that $M$ halts on all input, so that time complexity of $T_M(u)$ is defined not just for acceptable $u$ but also for unacceptable $u$. In this case, you can definitely compute $T_M(u)$ just by running it on all the input, and use this to take the max. But that wouldn't be constructible, which is why I thought maybe this is what you might actually have been interested in. But your reply to my comment says otherwise...

• I wonder whether one might be able to modify the argument to a relativized halting problem, using time bounds for the halting problem, and thereby make a counterexample of the type desired. Aug 5, 2018 at 20:11
• I have modified the question, trying to avoid the obstruction that you noticed. With that modification, I think the time function of a deterministic TM is constructible.
– user6976
Aug 5, 2018 at 20:33
• Your question is (almost?) equivalent to asking whether for a given $n$, there is $u$ of length $n$ for which the non-deterministic $M$ takes time $\ge t$. This is a decision question, where the (main) input $n$ is in unary. Unary languages (denoted $TALLY$) cannot be NP-complete, and what you're looking for seems to be a deterministic time bound for $TALLY\cap NP$, or rather, for $TALLY\cap NTIME(n^k)$. I would ask this on cstheory.SE. Aug 6, 2018 at 8:41
• @domotorp: Thank you! IIt would be easier for me to understand your comment if you convert it to an answer with references. For example, why TALLY cannot be NP-complete?
– user6976
Aug 6, 2018 at 11:05
• Oops, and now I see that I've commented on this answer instead of the original question - sorry! Aug 6, 2018 at 19:53

Your question is (almost?) equivalent to asking whether for a given $n$, there is $u$ of length $n$ for which the non-deterministic $M$ takes time $\ge t$. This is a decision question, where the (main) input $n$ is in unary. Unary languages (denoted $TALLY$) cannot be $NP$-complete, and what you're looking for seems to be a deterministic time bound for $TALLY\cap NP$, or rather, for $TALLY \cap NTIME(n^k)$. I would recommend asking this on cstheory.SE