The range of a non-computable function that grows faster than computable functions is undecidable
Let $f$ be a non-computable function that grows faster than every computable function. I have to prove that $R=\text{Range}(f)$ is non-decidable.
I'm trying to prove the statement by contradiction. Then the indicator function $1_R$ of $R$ is computable. Now, to get a contradiction, I want to find a computable function $g$ using $1_R$, s.t. $f$ doesn't grow faster than $g$. Can you please give me some tips on the construction of $g$?
P.S. A precise definition of $f$ is the following:
- $f$ is a non-computable totally defined $\mathbb{N}\rightarrow\mathbb{N}$ function
- Given a computable function $h$, there is $n_h\in\mathbb{N}$, s.t. for all $m\geq n_h$ we have $f(m)>h(m)$ (if $h(m)$ is defined)
For every set $A$, you can define the function $p_A$ that enumerates the elements of $A$ in increasing order, i.e. $p_A(0):= \min A$, $p_A(i+1) := \min (A \setminus \{ p_A(0),\dots, p_A(i) \})$.
Let $g=p_R$. If $1_R$ is computable then so is $g$: to compute $g(i)$ you look for the $(i+1)$-th natural number $n$ s.t. $1_R(n)=1$ (as $g(i)=n$ by definition).
It is not hard to show that $f$ does not grow faster than $g$. Let $i$ be s.t. $f(i)\neq g(i)$. If $g(i)<f(i)$ then, since $g$ is an enumeration of $R$ in increasing order, there must be some $j>i$ s.t. $f(j)=g(i)<g(j)$. Notice that if $f$ is strictly increasing then $f=g$.
There is general result saying that a set $R$ of natural numbers is semi-decidable iff $R$ is r.e. iff there as an $n$-adic partial recursive fct $f$ with $ran(f) = R$.