*This was [asked at MSE](https://math.stackexchange.com/questions/4182108/how-complicated-must-a-real-with-an-easy-total-computability-problem-be-to-com) without success. Granted, a bounty is still ongoing there, but it doesn't look like it will be answered.*




---


For (noncomputable) $A\subseteq\omega$ let $\tilde{A}=\{e: \varphi\_e^A\mbox{ is total and }\exists c(\varphi\_e^A\simeq\varphi\_c)\}$. A priori $\tilde{A}$ is $\Sigma^0\_3(A)$ ("$\varphi\_e^A$ is total and there is some $c$ such that on all inputs we eventually see agreement between $\varphi\_c$ and $\varphi\_e^A$"). However, this bound isn't sharp in general: [if $A$ is sufficiently Cohen generic then $\tilde{A}$ is $\Pi^0\_2(A)$](https://math.stackexchange.com/a/4179424/28111) *(of course we can't do better than this: $\tilde{A}$ is always $\Pi^0\_2(A)$-hard)*.


However, a fair amount of genericity (at a glance, $2$-genericity) is needed for that argument. This raises the question of how hard it must be to compute a real (nontrivially) satisfying "$\tilde{A}$ is not $\Sigma^0\_3(A)$-complete." Specifically:



> 
> Does every noncomputable $\Delta^0\_2$ set $A$ satisfy "$\tilde{A}$ is $\Sigma^0\_3$-complete"?
> 
> 
> 


Genericity-based arguments almost certainly won't be useful here, since there aren't even any $\Delta^0\_2$ *weak* $2$-generics.



Is there a $\Delta^0_2$ real with "easy total computability problem"?
It seems to me that if $G$ is 1-generic and recursive in $0'$ then $\tilde{G}$ is Boolean $\Sigma^0\_2$, which is sufficient to conclude that $\tilde{G}$ is not $\Sigma^0\_3(G)$-complete.


First, show that if (1) there is a condition $p$ in $G$ such that there is no $\varphi\_e$-splitting pair of conditions extending $p$ and (2) for every condition $q$ in $G$ and every $m$, there is an extension $r$ of $q$ which makes $\varphi\_e(m)$ converge, then $e$ is in $\tilde{G}$. We can exhibit a $\varphi\_c$ for $\varphi\_e(G)$ by observing that the value of $\varphi\_e(G)$ at $m$ can be recursively determined by searching for any extension of $p$ that gives a value at $m$. Second, show that if $e$ is in $\tilde{G}$ then (1) and (2) must hold. Obtaining (1) uses the 1-genericity of $G$ and obtaining (2) uses the totality of $\varphi\_e(G)$.


Since $G$ is $\Delta^0\_2$, Condition (1) is $\Sigma^0\_2$ and (2) is $\Pi^0\_2$, and so $\tilde{G}$ is Boolean $\Sigma^0\_2$.


