<p>I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so most generic sets are uncomputable.</p>
<p>However, if you go back to the <em>proof</em> that a given set of conditions was generic, and that it was strong enough to force the things you wanted it to force to build the oracle you wanted, you can often use that proof more directly to actually construct a particular oracle. And such oracles are often easily shown to be computable (though I suppose there are surely situations where they just aren't computable, but that seems less common to me).</p>
<p>A good exercise is to consider what a &quot;generics&quot; proof of Baker-Gill-Solovay looks like. One way is as follows. Define a condition <span class="math-container">$\sigma$</span> (i.e. partial function <span class="math-container">$\Sigma^* \to \{0,1\}$</span> to be a <span class="math-container">$\mathcal{BGS}$</span> condition if it contains at most one string of each length, and if <span class="math-container">$x \in dom(\sigma)$</span> and <span class="math-container">$|x|=|y|$</span>, then <span class="math-container">$y \in dom(\sigma)$</span>. Show that this is a notion of genericity, so <span class="math-container">$\mathcal{BGS}$</span>-generics exist, and show that it is strong enough to force the condition that the <span class="math-container">$n$</span>-th polytime Turing machine disagrees with the language <span class="math-container">$L^G = \{1^n : (\exists x \in G)[|x|=n]\} \in \mathsf{NP}^G$</span>.</p>
<p>Now look at your proof of the latter, and see how it is basically the same as BGS. But BGS just did it directly, and from the direct proof it's not hard to see that it's computable.</p>

CC BY-SA 4.0
2021-08-25T05:44:31.440Z
2021-08-25T05:44:31.440Z
Joshua Grochow
<p>In
<em>Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide</em>, <a href="http://dx.doi.org/10.1016/S0890-5401(03)00018-X" rel="nofollow noreferrer"><strong>An oracle builder’s toolkit</strong></a>, Inf. Comput. 182, No. 2, 95-136 (2003). <a href="https://zbmath.org/?q=an:1025.68041" rel="nofollow noreferrer">ZBL1025.68041</a>, the authors go through a variety of generic oracles.</p>
<p>The top answer to the following <a href="https://cstheory.stackexchange.com/questions/1675/relativization-with-respect-to-non-recursive-oracles">question</a> 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.</p>

<oracles><complexity><recursive>
Recursive generic oracles
veryinteresting
# Recursive generic oracles

(Asked by: username_0 on 2021-08-24)

In
*Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide*, [**An oracle builder’s toolkit**](http://dx.doi.org/10.1016/S0890-5401(03)00018-X), Inf. Comput. 182, No. 2, 95-136 (2003). [ZBL1025.68041](https://zbmath.org/?q=an:1025.68041), the authors go through a variety of generic oracles.

The top answer to the following [question](https://cstheory.stackexchange.com/questions/1675/relativization-with-respect-to-non-recursive-oracles) 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.

**Tags:** oracles, complexity, recursive

---

## 1 answers

### Answer by username_1 on 2021-08-25. Score: 3 | Accepted answer

I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so most generic sets are uncomputable.

However, if you go back to the *proof* that a given set of conditions was generic, and that it was strong enough to force the things you wanted it to force to build the oracle you wanted, you can often use that proof more directly to actually construct a particular oracle. And such oracles are often easily shown to be computable (though I suppose there are surely situations where they just aren't computable, but that seems less common to me).

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$.

Now look at your proof of the latter, and see how it is basically the same as BGS. But BGS just did it directly, and from the direct proof it's not hard to see that it's computable.


---

