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

  • $\begingroup$ I assume that (i) we are to find f that depends on g and c, and (ii) c must be greater than 1. $\endgroup$ – Charles Stewart Sep 3 '10 at 16:53
  • $\begingroup$ I interpreted the question as: for every g and c s.t. ... there is an f s.t. ... $\endgroup$ – Kaveh Sep 3 '10 at 16:56
  • $\begingroup$ But Noam's interpretation also makes sense: is there g, c, and f s.t. ... . and is more reasonable considering the title. $\endgroup$ – Kaveh Sep 3 '10 at 17:04
  • 5
    $\begingroup$ This can be a nice exercise in a "computability course": show that for some g there exist such f and for others not... $\endgroup$ – Noam Sep 3 '10 at 18:01
  • $\begingroup$ @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. $\endgroup$ – Charles Stewart Sep 3 '10 at 19:26

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

  • $\begingroup$ I think you don't get to choose g. $\endgroup$ – Charles Stewart Sep 3 '10 at 16:50
  • 5
    $\begingroup$ 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)}. $\endgroup$ – 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.