A function dominating all total recursive functions

Question

I am trying to solve the following problem: If A is a recursively enumerable set but it is not recursive, there is a function $f: \mathbb{N} \rightarrow \mathbb{N}$ (not necessarily recursive) that eventually dominates each total recursive function $g$ but $A$ is not recursive in $f$. I tried to used an injury method to construct such function, but it did not work. Any suggestion to solve this problem would be highly appreciated. More in general I also want to know, how one could build a function dominating all the total recursive functions? Do we know something about the degree if such function?
Thanks in advance for your help!

Answer 1

Since it is not required that $f$ is recursive, we can be as recklessly nonconstructive as we want while defining it, so we can just wing it:

Suppose $\phi_1,\phi_2,\phi_3,\ldots$ is an enumeration of all total recursive functions, and $M_1, M_2, M_3, \ldots$ enumerates all recipes for oracle machines parameterized by an $\mathbb N\to \mathbb N$ oracle.

We proceed in steps. In step $n$ we have already decided the value of $f(x)$ for all $x<k$ for some $k$. Our task in this step is on one hand to make sure $f$ eventually dominates $\phi_n$, and on the other hand to make sure that $M_n(f)$ does not decide $A$.

For the first of these we simply decide that $f(x)$ must be at least $1+\max_{i\le n}\phi_i(x)$ for all $x\ge k$. Call a function that satisfies this condition (and agrees with the already-decided values) admissible. The pointwise smallest admissible function is $$ f^\circ(x) = \begin{cases} f(x) & \text{for }x<k \\ 1+\max_{i\le n}\phi_i(x) & \text{otherwise} \end{cases} $$ which is obviously computable.

The second task is a bit more involved. First ask ourselves if there is any admissible $f^\times$ and any $y$ such that $M_n(f^\times)(y)$ halts in finite time and gives the wrong answer to whether $y\in A$. If that is the case, then increase $k$ enough that it is larger than every argument to $f^\times$ in a call made by $M_n(f^\times)(y)$, decide that $f(x)=f^\times(x)$ for all $x$ less than this new $k$, and go to the step for the next $n$.

Otherwise, I claim, we can be happy because there is no admissible $f^+$ such that $M(f^+)$ is even total. (So just increase $k$ by one and go to the next $n$).

Namely, suppose for a contradiction that $f^+$ exists but there is no pair of $f^\times$ and $y$ combination that ever makes $M_n$ give a wrong result. Then we could decide $A$ by an ordinary Turing machine that does a breath-first search through all possible runs of $M_n$ where its oracle gives admissible responses (here it is important that $f^\circ$ is computable), until a terminating run is found. A terminating run would always exist, because that's what $f^+$ gives us, and we have explicitly assumed that a terminating run always gives the correct answer.

---

Hmm, this construction doesn't seem to need the assumption that $A$ is r.e. I wonder if I've overlooked anything along the way.