Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable?
Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function.
No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = K(s(x))$, where $s(x)$ is some string representation for $x$. Then $|s(x)| \approx \ln(x)$ and $K(s) \leq |s(x)| + c$ for some $c$ so $f(x)$ is polynomially bounded but incomputable. QED
Let $\Omega \in [0,1)$ be an uncomputable real number, and $f(n)$ be the $n$th digit in the binary representation of $\Omega$. Obviously $f=O(1)$, which is about as tightly bounded as you can get. But computing $f$ is equivalent to computing $\Omega$, so $f$ is uncomputable.