<p>It’s not clear to me whether you want a particular pair of functions <em>f</em> and <em>g</em> with the desired property, or if you’re asking if, for every uncomputable <em>g</em>, there exists a computable <em>f</em> &isin; &Theta;(<em>g</em>).</p>

<p>In the first case, Noam’s answer applies. Otherwise, the answer is no: just let <em>g</em> be growing faster than every computable function (standard example: the <a href="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow">busy beaver function</a>).</p>

CC BY-SA 2.5
2010-09-03T18:57:50.710Z
+1 Thanks, for the answer. The interpretation I had intended was the former, whether such a $f$ and $g$ exist
Travis Service
CC BY-SA 2.5
2010-09-03T16:51:11.693Z
2010-09-05T02:13:50.063Z
2010-09-05T02:13:50.063Z
Antonio E. Porreca
<p>Sure: just take g(n) = n + halt(n) (where halt(n)=1 if TM number n halts, and 0 ow).</p>

CC BY-SA 2.5
2010-09-03T16:50:39.917Z
I think you don't get to choose g.
Charles Stewart
CC BY-SA 2.5
2010-09-03T17:52:51.723Z
I take "can there be" to ask whether for some g there exists an f.
For the interpretation of whether for every g there exists an f, you get a negative answer by taking g=n^{halt(n)}.
Noam
CC BY-SA 2.5
2010-09-03T16:42:12.383Z
2010-09-03T16:42:12.383Z
Noam
<p>This question most likely has a simple answer; however, I do not see it.</p>

<p>Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that, for all $n$ large enough: $g(n) \leq f(n) \leq c \cdot g(n)$ (that is $f(n) = \Theta(g(n)$)?</p>

CC BY-SA 2.5
2010-09-03T16:53:06.730Z
I assume that (i) we are to find f that depends on g and c, and (ii) c must be greater than 1.
Charles Stewart
CC BY-SA 2.5
2010-09-03T16:56:58.267Z
I interpreted the question as: for every g and c s.t. ... there is an f s.t. ...
Kaveh
CC BY-SA 2.5
2010-09-03T17:04:04.977Z
But Noam's interpretation also makes sense: is there g, c, and f s.t. ... . and is more reasonable considering the title.
Kaveh
CC BY-SA 2.5
2010-09-03T18:01:36.507Z
This can be a nice exercise in a "computability course": show that for some g there exist such f and for others not...
Noam
CC BY-SA 2.5
2010-09-03T19:26:26.243Z
@Kaveh: I don't see it.  At least I see the closeness to the title, but "Let g:N→N be an uncomputable function" is well-established terminology unambiguously indicating that g is an unknown.
Charles Stewart
CC BY-SA 2.5
2010-09-03T20:34:41.720Z
@Charles: I agree with you that "g" seems to be an arbitrary given function, that was how I interpreted the question at first without paying attention to the title.
Kaveh
<computability>
Computable function $f = \Theta(g)$ with $g$ uncomputable
Travis Service
# Computable function $f = \Theta(g)$ with $g$ uncomputable

(Asked by: username_0 on 2010-09-03)

This question most likely has a simple answer; however, I do not see it.

Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that, for all $n$ large enough: $g(n) \leq f(n) \leq c \cdot g(n)$ (that is $f(n) = \Theta(g(n)$)?

**Tags:** computability

> **Comments:**
> **username_1**: I assume that (i) we are to find f that depends on g and c, and (ii) c must be greater than 1.  
> **username_2**: I interpreted the question as: for every g and c s.t. ... there is an f s.t. ...  
> **username_2**: But username_3's interpretation also makes sense: is there g, c, and f s.t. ... . and is more reasonable considering the title.  
> **username_3**: This can be a nice exercise in a "computability course": show that for some g there exist such f and for others not...  
> **username_1**: @username_2: I don't see it.  At least I see the closeness to the title, but "Let g:N→N be an uncomputable function" is well-established terminology unambiguously indicating that g is an unknown.  
> **username_2**: @Charles: I agree with you that "g" seems to be an arbitrary given function, that was how I interpreted the question at first without paying attention to the title.  

---

## 2 answers

### Answer by username_3 on 2010-09-03. Score: 24 | Accepted answer

Sure: just take g(n) = n + halt(n) (where halt(n)=1 if TM number n halts, and 0 ow).

> **Comments:**
> **username_1**: I think you don't get to choose g.  
> **username_3**: I take "can there be" to ask whether for some g there exists an f. For the interpretation of whether for every g there exists an f, you get a negative answer by taking g=n^{halt(n)}.  

---

### Answer by username_4 on 2010-09-03. Score: 9

It’s not clear to me whether you want a particular pair of functions *f* and *g* with the desired property, or if you’re asking if, for every uncomputable *g*, there exists a computable *f* ∈ Θ(*g*).

In the first case, username_3’s answer applies. Otherwise, the answer is no: just let *g* be growing faster than every computable function (standard example: the [busy beaver function](http://en.wikipedia.org/wiki/Busy_beaver)).

> **Comments:**
> **username_0**: +1 Thanks, for the answer. The interpretation I had intended was the former, whether such a $f$ and $g$ exist  

---

