<p>From the comment: </p>

<p>In "<a href="http://cage.ugent.be/~klein/papers/turing.pdf">Deterministic Turing Machines in the Range between Real-Time and Linear-Time</a>" I found:</p>

<p>... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...</p>

CC BY-SA 3.0
2013-03-28T12:14:54.830Z
What is $T^{-1}(DTM)$?
Emil Jeřábek
CC BY-SA 3.0
2013-03-28T13:23:48.537Z
$T^{-1}(DTM)$ is the inverse of an increasing, unbounded time-constructible function $f$ ( $\forall c \in \mathbb{N}, \exists n_0, c' \in \mathbb{N}$ s.t $\forall n \geq n_0$ we have $c f(n) \leq f(c'n)$ ). You can replace it with a honest sublinear function.
Marzio De Biasi
CC BY-SA 3.0
2013-03-28T11:16:43.520Z
2013-03-28T11:16:43.520Z
Marzio De Biasi
<p>Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice that there is no $O(\cdot)$ around $f(n) + 1$.</p>

<p>Is it true that $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?</p>

<p>Using the <a href="https://en.wikipedia.org/wiki/Linear_speedup_theorem">linear speed-up theorem</a>, we can prove $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$, but can we reach $n$?</p>

<p>It seems that the language of palindromes is in $\mathsf{DTIME}(n)$; for related topics, see <a href="http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/">Lipton's blog post about string algorithms</a></p>

CC BY-SA 3.0
2013-03-27T23:03:53.000Z
In "[Deterministic Turing Machines in the Range between Real-Time and Linear-Time](http://cage.ugent.be/~klein/papers/turing.pdf)" I found: if $r \in T^{-1}(DTM)$ and $r'\in o(r)$ then $DTIME(n + r') \subset DTIME(n + r)$
Marzio De Biasi
CC BY-SA 3.0
2013-03-28T10:16:12.330Z
Nice, seems to be just what I was looking for. Do you want to convert it into an answer?
domotorp
CC BY-SA 3.0
2013-09-05T17:44:31.713Z
interesting question but object to the redefinition of a [standard complexity class DTIME](http://en.wikipedia.org/wiki/Time_hierarchy_theorem) in a nonstandard way, suggest you at least call it something like DTIME' to avoid confusion
vzn
CC BY-SA 3.0
2013-10-25T02:14:22.937Z
This paper maybe helpful. [Rosenberg 67] Real-Time Definable Languages
http://dl.acm.org/citation.cfm?id=321423
zZzZzZ
<cc.complexity-theory><time-complexity><turing-machines><time-hierarchy>
Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?
domotorp
# Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

(Asked by: username_0 on 2013-03-27)

Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice that there is no $O(\cdot)$ around $f(n) + 1$.

Is it true that $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Using the [linear speed-up theorem](https://en.wikipedia.org/wiki/Linear_speedup_theorem), we can prove $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$, but can we reach $n$?

It seems that the language of palindromes is in $\mathsf{DTIME}(n)$; for related topics, see [Lipton's blog post about string algorithms](http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/)

**Tags:** cc.complexity-theory, time-complexity, turing-machines, time-hierarchy

> **Comments:**
> **username_1**: In "[Deterministic Turing Machines in the Range between Real-Time and Linear-Time](http://cage.ugent.be/~klein/papers/turing.pdf)" I found: if $r \in T^{-1}(DTM)$ and $r'\in o(r)$ then $DTIME(n + r') \subset DTIME(n + r)$  
> **username_0**: Nice, seems to be just what I was looking for. Do you want to convert it into an answer?  
> **username_2**: interesting question but object to the redefinition of a [standard complexity class DTIME](http://en.wikipedia.org/wiki/Time_hierarchy_theorem) in a nonstandard way, suggest you at least call it something like DTIME' to avoid confusion  
> **username_3**: This paper maybe helpful. [Rosenberg 67] Real-Time Definable Languages http://dl.acm.org/citation.cfm?id=321423  

---

## 1 answers

### Answer by username_1 on 2013-03-28. Score: 12 | Accepted answer

From the comment:

In "[Deterministic Turing Machines in the Range between Real-Time and Linear-Time](http://cage.ugent.be/~klein/papers/turing.pdf)" I found:

... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...

> **Comments:**
> **username_4**: What is $T^{-1}(DTM)$?  
> **username_1**: $T^{-1}(DTM)$ is the inverse of an increasing, unbounded time-constructible function $f$ ( $\forall c \in \mathbb{N}, \exists n_0, c' \in \mathbb{N}$ s.t $\forall n \geq n_0$ we have $c f(n) \leq f(c'n)$ ). You can replace it with a honest sublinear function.  

---

