# 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

## 2 Answers

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

• I think you don't get to choose g. – Charles Stewart Sep 3 '10 at 16:50
• 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 Sep 3 '10 at 17:52

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, Noam’s answer applies. Otherwise, the answer is no: just let g be growing faster than every computable function (standard example: the busy beaver function).

• +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