<p>Since the Wikipedia article doesn't give the proof and the paper is on ACM DL I thought that it might be useful to post the proof here:</p>

<blockquote>
  <p>THEOREM 3.7. (Gap Theorem). </p>
  
  <p>Let $\Phi$ be a complexity measure, $g$ a nondecreasing recursive function such that $\forall x, g(x) \geq x$. Then there exists an increasing recursive function $t$ such that functions computable of complexity measure $t$ are the same as functions computable of complexity measure $g\circ t$.</p>
  
  <p>PROOF.</p>
  
  <p>Define $t$ as follows:</p>
  
  <p>$$t(0) := 1$$
  $$t(n) := \mu{ k &gt; t(n-1)}: \forall i \leq n, (\Phi_i(n)&lt;k  \lor \Phi_i(n)&gt; g(k) )$$</p>
  
  <ol>
  <li><p>for all $n$, there is a $k$, since for all $i \leq n$: </p>
  
  <p>a. if $\Phi_i(n)$ is undefined then $\forall k, \Phi_i(n)&gt;g(k)$, and</p>
  
  <p>b. if  $\Phi_i(n)$ defined then $\exists k, \Phi_i(n) &lt; k$. </p></li>
  <li><p>$k$ can be found recursively, since $\Phi$ is a complexity measure and thus $\Phi_i(n) &lt;k$ and $\Phi_i(n) &gt; g(k)$ are recursive predicates.</p></li>
  <li><p>$t$ satisfies the theorem, since $n \geq i$ implies that either $\Phi_i(n) &lt; t(n)$ or 
  $\Phi_i(n) &gt; g \circ t(n)$. </p></li>
  </ol>
  
  <p>QED.</p>
  
  <p>We observe that an arbitrarily large $t$ can be found to satisfy Theorem 3.7. Suppose we want $t(n) &gt; r(n)$, then define </p>
  
  <p>$$t(0) := r(0) + 1$$ 
  $$t(n) := \mu{k &gt; max\{t(n-1), r(n)\}}: \ldots$$ </p>
</blockquote>

<p>(from Allan Borodin, "<a href="http://dx.doi.org/10.1145/321679.321691" rel="nofollow">Computational complexity and the existence of complexity gaps</a>", JACM 1972, with slight modifications.)</p>

CC BY-SA 3.0
2011-10-13T07:47:29.160Z
The idea is to define $t(n)$ to be the least $k$ s.t. any function (of index less than $n$) that is computable in complexity measure $g(k)$ is also computable in complexity measure $k$.
Kaveh
CC BY-SA 3.0
2011-10-12T22:19:27.390Z
2011-10-17T15:07:35.513Z
2011-10-17T15:07:35.513Z
Kaveh
<p><a href="http://dx.doi.org/10.1145%2F321679.321691">Borodin's Gap Theorem</a>: For every total computable function $g(n) \geq n$, there is a total computable function $t$ such that $DTIME[g(t(n))] = DTIME[t(n)]$. </p>

<p>In fact, this holds for any Blum complexity measure in place of $DTIME$. </p>

<p>See also <a href="http://en.wikipedia.org/wiki/Gap_theorem">the wikipedia page</a> and references therein.</p>

CC BY-SA 3.0
2011-10-12T04:37:11.450Z
2011-10-12T04:37:11.450Z
Joshua Grochow
<p>In the Arora-Barak book, in the definition of time constructible functions, it is said that using functions that are not time constructible can lead to "anomalous results". Does anyone have an example of such an "anomalous result"? I have heard in particular that there might exist functions such that the time hierarchy theorem does not hold, does anyone have an example of such functions? Is there something about this somewhere in the litterature?</p>

CC BY-SA 3.0
2011-10-11T21:59:51.450Z
Have you had a look at these: http://math.stackexchange.com/questions/51082/definition-of-time-constructible-function and http://cstheory.stackexchange.com/questions/992/an-explicit-separation-between-time-constructibility-and-space-constructibility ?
Jukka Suomela
CC BY-SA 3.0
2011-10-12T06:30:45.393Z
@JukkaSuomela: Yes I have, but they are about which functions are time/space constructible and why they are useful.
Pascal
<cc.complexity-theory>
Non constructible functions and anomalous results
Pascal
# Non constructible functions and anomalous results

(Asked by: username_0 on 2011-10-11)

In the Arora-Barak book, in the definition of time constructible functions, it is said that using functions that are not time constructible can lead to "anomalous results". Does anyone have an example of such an "anomalous result"? I have heard in particular that there might exist functions such that the time hierarchy theorem does not hold, does anyone have an example of such functions? Is there something about this somewhere in the litterature?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Have you had a look at these: http://math.stackexchange.com/questions/51082/definition-of-time-constructible-function and http://cstheory.stackexchange.com/questions/992/an-explicit-separation-between-time-constructibility-and-space-constructibility ?  
> **username_0**: @JukkaSuomela: Yes I have, but they are about which functions are time/space constructible and why they are useful.  

---

## 2 answers

### Answer by username_3 on 2011-10-12. Score: 11 | Accepted answer

[Borodin's Gap Theorem](http://dx.doi.org/10.1145%2F321679.321691): For every total computable function $g(n) \geq n$, there is a total computable function $t$ such that $DTIME[g(t(n))] = DTIME[t(n)]$.

In fact, this holds for any Blum complexity measure in place of $DTIME$.

See also [the wikipedia page](http://en.wikipedia.org/wiki/Gap_theorem) and references therein.


---

### Answer by username_2 on 2011-10-12. Score: 6

Since the Wikipedia article doesn't give the proof and the paper is on ACM DL I thought that it might be useful to post the proof here:

> THEOREM 3.7. (Gap Theorem).
>
> Let $\Phi$ be a complexity measure, $g$ a nondecreasing recursive function such that $\forall x, g(x) \geq x$. Then there exists an increasing recursive function $t$ such that functions computable of complexity measure $t$ are the same as functions computable of complexity measure $g\circ t$.
>
> PROOF.
>
> Define $t$ as follows:
>
> $$t(0) := 1$$
> $$t(n) := \mu{ k > t(n-1)}: \forall i \leq n, (\Phi\_i(n) g(k) )$$
>
> 1. for all $n$, there is a $k$, since for all $i \leq n$:
>
>    a. if $\Phi\_i(n)$ is undefined then $\forall k, \Phi\_i(n)>g(k)$, and
>
>    b. if $\Phi\_i(n)$ defined then $\exists k, \Phi\_i(n) < k$.
> 2. $k$ can be found recursively, since $\Phi$ is a complexity measure and thus $\Phi\_i(n)  g(k)$ are recursive predicates.
> 3. $t$ satisfies the theorem, since $n \geq i$ implies that either $\Phi\_i(n) < t(n)$ or
>    $\Phi\_i(n) > g \circ t(n)$.
>
> QED.
>
> We observe that an arbitrarily large $t$ can be found to satisfy Theorem 3.7. Suppose we want $t(n) > r(n)$, then define
>
> $$t(0) := r(0) + 1$$
> $$t(n) := \mu{k > max\{t(n-1), r(n)\}}: \ldots$$

(from Allan Borodin, "[Computational complexity and the existence of complexity gaps](http://dx.doi.org/10.1145/321679.321691)", JACM 1972, with slight modifications.)

> **Comments:**
> **username_2**: The idea is to define $t(n)$ to be the least $k$ s.t. any function (of index less than $n$) that is computable in complexity measure $g(k)$ is also computable in complexity measure $k$.  

---

