6
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\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
    Commented Sep 3, 2010 at 16:53
  • $\begingroup$ I interpreted the question as: for every g and c s.t. ... there is an f s.t. ... $\endgroup$
    – Kaveh
    Commented Sep 3, 2010 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
    Commented Sep 3, 2010 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
    Commented Sep 3, 2010 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
    Commented Sep 3, 2010 at 19:26

2 Answers 2

Reset to default
24
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think you don't get to choose g. $\endgroup$
    – Charles Stewart
    Commented Sep 3, 2010 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
    Commented Sep 3, 2010 at 17:52
9
$\begingroup$

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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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