Runtime of a TM enumerator

Question

Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)?

For simplicity let's say the string is binary, the obvious answer is exponential to input length. But the question is can we do better?

(Sorry if I mixed up some notations, been a while since my Theory of Computation class.)

I somehow feel like I can make something out of

• Are runtime bounds in P decidable? (answer: no)

but can someone please give a hint?

Answer 1

If you weaken the time bound very slightly from linear, the answer is definitively no. Probably a more delicate construction will work for linear time.

Let $f(n)$ be any monotone increasing time-constructible function $\geq n$. Then there is a language $L \in \mathsf{DTIME}(n^2)$ (in fact, in time $n f^{-1}(n)$, e.g. when $f(n)=2^n$ this is $n \log n$) such that any enumerator for that language requires $f(n)$ delay between enumerating the $n$-th and $(n+1)$-st strings. In particular, $L = \{0^{f(m)} : m \geq 0\}$ has this property.

$L$ can be decided in time $n f^{-1}(n)$: if $x \neq 0^{n}$ then $x \notin L$. Otherwise, compute $f(1), f(2), \dotsc$ until $f(k) \geq n$. In fact, in the computation of $f(k)$, if the counter ever surpasses $n$, stop. This ensures that each computation of $f(i)$ takes at most time $n$. The largest $k$ for which such a computation needs to be done is $\lceil f^{-1}(n) \rceil$, giving the claimed runtime.

Finally, any enumerator for $L$ requires delay $f(n)$ between strings in the worst case. If the enumerator enumerates $L$ in lexicographic order, this clear because it takes time $f(n)$ to just write down the next string. If the enumerator is out of order finitely often, the same is still true after the finitely many. If the enumerator is out of order infinitely often, then infinitely often it is enumerating longer strings earlier than otherwise, hence takes time more than $f(n)$.

Answer 2

In your question, the phrase "the TM" is not well defined. Let's assume you meant that the language is decidable in $O(n)$.

If this is the case, the problem is undecidable. Here is a reduction from the halting problem.

Given a TM $M$, construct the following enumerator: it outputs $0$, then, in iteration $i$, it runs $M$ on $\epsilon$ for $i$ steps, and prints $0^i$ afterwords, and then increases $i$ by $1$. If at any point $M$ halts, it outputs the strings $0^i$ for all $i\ge 0$, one by one.

Now, even deciding whether there is a finite bound between words is equivalent to deciding if $M$ halts. Indeed, if $M$ halts, then its runtime is the bound on consecutive words. Otherwise, there is no bound. However, the language is always the same: $0^*$, which is decidable in Linear time.