Let $f:{\mathbb N}\to{\mathbb N}$ be an arbitrary function. Is there always a computable function $g:{\mathbb N}\to{\mathbb N}$ such that $g \geq f$ (i.e. $g(n)\geq f(n)$ for every $n$) ?
The answer is clearly no for primitive recursive functions, as shown by the famous Ackermann function.
There is no such computable function $g$. The proof is by a variant of the Cantor diagonal argument.
Let $h_0,h_1,h_2, h_3,\dots$ be a list of all the computable functions. Define the function $f$ by $f(n)=h_n(n)+1$. There is no computable function $g$ such that $g(n)\ge f(n)$ for all $n$. For if $g$ is computable it is $h_N$ for some $N$.
