<p>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.</p>

<p>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 <em>any</em> 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. </p>

<p>$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.</p>

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

CC BY-SA 3.0
2013-03-27T23:27:15.540Z
2013-03-27T23:27:15.540Z
Joshua Grochow
<p>In your question, the phrase "the TM" is not well defined. Let's assume you meant that the language is decidable in $O(n)$.</p>

<p>If this is the case, the problem is undecidable. Here is a reduction from the halting problem.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-02-25T22:28:40.340Z
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"
Sasho Nikolov
CC BY-SA 3.0
2013-02-26T06:58:58.607Z
I interpreted "is there a way to find" as "is it computable". You might be right, and we need clarification from the OP.
Shaull
CC BY-SA 3.0
2013-02-25T21:41:33.393Z
2013-02-25T21:41:33.393Z
Shaull
<p>Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that <em>decides</em> this language is promised to run in linear time)?</p>

<p>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? </p>

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

<p>I somehow feel like I can make something out of </p>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no">Are runtime bounds in P decidable? (answer: no)</a> </li>
</ul>

<p>but can someone please give a hint?</p>

CC BY-SA 3.0
2013-02-25T04:27:59.000Z
Perhaps more appropriate to cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2013-02-25T06:07:59.237Z
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?
vzn
CC BY-SA 3.0
2013-02-25T06:49:13.820Z
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.
Shaull
CC BY-SA 3.0
2013-02-25T17:22:32.450Z
@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.
fy_iceworld
CC BY-SA 3.0
2013-02-25T17:23:59.640Z
@Shaull Now I'm thinking about it.. Yea it might not be exponential.. So I guess this is totally depending on the language?
fy_iceworld
CC BY-SA 3.0
2013-02-25T21:35:07.790Z
Even if you fix the language, it is dependent on which enumerator you use.
Shaull
CC BY-SA 3.0
2013-02-26T18:05:11.373Z
Perhaps I didn't understand well the question, but if you're asking about a generic enumerator, then the time between two outputs (2 strings in L) can be arbitrary (for example run the ackermann function before producing the next string). If you're asking about the *density* of the strings in $L$ then there are some results; in particular, for regular languages, you can take a look at: ["Characterizing Regular Languages with Polynomial Densities"](ftp://ftp.csd.uwo.ca/pub/csd-technical-reports/309/report.ps)
Marzio De Biasi
<computability><turing-machines><polynomial-time>
Runtime of a TM enumerator
fy_iceworld
# Runtime of a TM enumerator

(Asked by: username_0 on 2013-02-25)

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)](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no)

but can someone please give a hint?

**Tags:** computability, turing-machines, polynomial-time
> **Comments:**
> **username_1**: Perhaps more appropriate to cs.stackexchange.  
> **username_2**: 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?  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_0**: @Shaull Now I'm thinking about it.. Yea it might not be exponential.. So I guess this is totally depending on the language?  
> **username_3**: Even if you fix the language, it is dependent on which enumerator you use.  
> **username_4**: Perhaps I didn't understand well the question, but if you're asking about a generic enumerator, then the time between two outputs (2 strings in L) can be arbitrary (for example run the ackermann function before producing the next string). If you're asking about the *density* of the strings in $L$ then there are some results; in particular, for regular languages, you can take a look at: ["Characterizing Regular Languages with Polynomial Densities"](ftp://ftp.csd.uwo.ca/pub/csd-technical-reports/309/report.ps)  

---

## 2 answers

### Answer by username_5 on 2013-03-27. Score: 3

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 by username_3 on 2013-02-25. Score: 0

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.

> **Comments:**
> **username_6**: 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"  
> **username_3**: I interpreted "is there a way to find" as "is it computable". You might be right, and we need clarification from the OP.  

---

