Can we computably escape infinitely many functions (allowing partiality)?

Question

Let $(p_i)_{i\in\omega}$ be a uniformly computable sequence of partial functions (i.e. the partial function $q(i,x)=p_i(x)$ is computable) such that infinitely many $p_i$s are total. Must there be a total computable function $f$ which escapes infinitely many of the total $p_i$s?

If we replace "escape" by "dominate" then this has an easy negative answer. First, WLOG assume that if $p_i(x)$ halts it halts in at most $p_i(x)$-many steps (we can arrange this by shifting from the $p_i$s themselves to the sums of the $p_i$s with their running times). Now if $f$ is a total computable function, then $D_f$ is $\Sigma^0_2$: we have $i\in D_f$ iff, aside from finitely many exceptions, each $n$ has the property that $p_i(n)$ halts in at most $f(n)$ steps and outputs a value $\le f(n)$. (This is where the runtime assumption above comes in.)

We then wrap things up by using the $\Pi^0_2$ completeness of totality and the existence of an infinite $\Pi^0_2$ set with no infinite $\Sigma^0_2$ subset (basically, a co-simple set relativized to $0'$).

However, this approach breaks down completely if we try to replace "dominates" with "escapes" - the second characterization becomes again $\Pi^0_2$, and so doesn't provide any leverage. I still suspect the answer is negative, but I don't immediately see how to prove it.

Answer 1

No. In fact, we can make a uniformly computable sequence of partial functions such that every total computable function is majorized by all but finitely many of the total functions in the sequence. Then any escaping function of the sort you're after would escape all total computable functions, and would thus have hyperimmune degree.

We'll do this using a priority tree construction. On the tree we have $P_n$-nodes and $R_e$-nodes, for $n, e \in \omega$.

A $P_n$-node chooses a unique $i$ and builds $p_i$ -- every time the node is visited during the construction, it extends $p_i$ by one value, larger than any value yet seen. The node has only a single outcome.

An $R_e$-node simply controls the flow of the priority. It has two outcomes, $\infty$ and fin, and it is guessing whether $\varphi_e$ is total. It takes the fin outcome until it sees $\varphi_e(0)$ converge, then it takes the $\infty$ outcome for one stage, then takes the fin outcome until it sees $\varphi_e(1)$ converge, etc. Whenever it takes the $\infty$ outcome, it initializes all $P_n$-nodes below its fin outcome, meaning those requirements must choose new $i$s.

Define a true path as usual, and note that each $P_n$-node along the true path defines a total function in our sequence, and these are the only total functions in the sequence.

Suppose $\varphi_e$ is total. Consider the $R_e$-node $\sigma$ on the true path. Note that every $P_n$-node extending $\sigma\infty$ defines its function slower than $\varphi_e$ converges, and so since it chooses large values, its function will majorize $\varphi_e$. Thus almost every total function in the sequence majorizes $\varphi_e$.