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

but can someone please give a hint?

  • 1
    $\begingroup$ Perhaps more appropriate to cs.stackexchange. $\endgroup$ – Yuval Filmus Feb 25 '13 at 4:27
  • $\begingroup$ the 1st sentence does not really seem to make sense. a time bound is associated with a TM. what is "a time bound between 2 consecutive strings enumerated by a TM"? is that the time it takes between enumerating consecutive strings? $\endgroup$ – vzn Feb 25 '13 at 6:07
  • 2
    $\begingroup$ Why is it obvious that this can be done in exponential time? The enumerator you get might no work in linear time. In fact, there might not even be a finite bound. It is easy to construct an enumerator that increases the bound manually. $\endgroup$ – Shaull Feb 25 '13 at 6:49
  • $\begingroup$ @vzn I meant the time interval between 2 consecutive strings, enumerating the string themselves takes O(n) so that doesn't really matter, I'm looking at the time between the last character of first string and the first character of the second string. $\endgroup$ – zee Feb 25 '13 at 17:22
  • $\begingroup$ @Shaull Now I'm thinking about it.. Yea it might not be exponential.. So I guess this is totally depending on the language? $\endgroup$ – zee Feb 25 '13 at 17:23

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


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.

  • 3
    $\begingroup$ I thought the question was "assuming $L$ is decidable in linear time, does there exist an enumerator with say exponential incremental complexity?". you are answering "is the incremental complexity of every enumerator for every language in DTIME(n) decidable" $\endgroup$ – Sasho Nikolov Feb 25 '13 at 22:28
  • $\begingroup$ I interpreted "is there a way to find" as "is it computable". You might be right, and we need clarification from the OP. $\endgroup$ – Shaull Feb 26 '13 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.