# Computable function $f = \Theta(g)$ with $g$ uncomputable

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

• 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 Sep 3 '10 at 16:53
• I interpreted the question as: for every g and c s.t. ... there is an f s.t. ... – Kaveh Sep 3 '10 at 16:56
• But Noam's interpretation also makes sense: is there g, c, and f s.t. ... . and is more reasonable considering the title. – Kaveh Sep 3 '10 at 17:04
• This can be a nice exercise in a "computability course": show that for some g there exist such f and for others not... – Noam Sep 3 '10 at 18:01
• @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 Sep 3 '10 at 19:26

• +1 Thanks, for the answer. The interpretation I had intended was the former, whether such a $f$ and $g$ exist – Travis Service Sep 3 '10 at 18:57