# How to approximate non-computably recursive set by computably recursive set

let $J=S \cap D$,$G=S \cup D$,sort $G$,$a_n \in G$.

Function $\gamma (n,s)=\frac{\Sigma_{a_i \in J}^n a_i^s}{\Sigma_{i=1}^n a_i^s}$.

Given S ,a non computably enumerable set,is there a computably enumerable set D Such that $\lim_{n \to \infty}\gamma (\infty,0)=1$? Or under what condition $\lim_{n \to \infty}\gamma (\infty,0)=\frac {1}{2}$,and so on?

If such limit does not exist,is it bounded? $L \leq \gamma (n,0) \leq M$?

Especially when S is productive set or immune set,can we approximate S by such a approach? Are there any results about such questions?

A logician expresses the question as how about $\inf \lim_n\frac{ |\{m\leq n \mid m\in S \cap D\}|} {|\{m\leq n\mid m \in S \cup D\}|}$ ?

-

## 2 Answers

If $S$ is selected randomly under the fair-coin (Lebesgue-Cantor) measure on $2^\omega$ then $S$ will be immune and $S$ will asymptotically contain $1/2$ of the elements of $D$, plus $1/2$ of the elements of $\omega\backslash D$. To get this to be true for all recursively enumerable $D$ it is enough that $S$ is 2-random (Martin-Löf random relative to $0'$). For background you can look at the recent books Downey and Hirschfeldt, Algorithmic randomness and complexity, and Nies, Computability and randomness.

-

I think that there exists an immune $S$ for which this limit is always 0 (for all $D$). The construction (using the priority method) is in my appendix to a new paper of Olshanskii which should be in the arXiv soon. If you really need it, I can send you the text by email. It is about 3 pages long.

-