# Recursive generic oracles

In Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles.

The top answer to the following question mentions that generic oracles tend to not be recursive, but can be made recursive. How does one go about making such a change? Does the technique generalize to all types of X-generic oracles? I'm particularly interested in making sp-generic oracles recursive, but I'm interested in other types of genericity as well.

A good exercise is to consider what a "generics" proof of Baker-Gill-Solovay looks like. One way is as follows. Define a condition $$\sigma$$ (i.e. partial function $$\Sigma^* \to \{0,1\}$$ to be a $$\mathcal{BGS}$$ condition if it contains at most one string of each length, and if $$x \in dom(\sigma)$$ and $$|x|=|y|$$, then $$y \in dom(\sigma)$$. Show that this is a notion of genericity, so $$\mathcal{BGS}$$-generics exist, and show that it is strong enough to force the condition that the $$n$$-th polytime Turing machine disagrees with the language $$L^G = \{1^n : (\exists x \in G)[|x|=n]\} \in \mathsf{NP}^G$$.