Are finite subsets of bi-immune sets random? Let $A$ be a bi-immune set, that is, an immune set whose complement is also immune. An immune set (let's say $A$) is a set of natural numbers (the natural numbers include 0) such that: i. $A$ is infinite, and ii. for every infinite r.e. set $B$, $B$ $\cap$ $\overline A$ $\ne$ $\emptyset$.
Question:  Are the finite subsets of bi-immune sets 'random', and if so, what is the proper notion of 'randomness' for such finite sets?
 A: List all the infinite r.e. sets as $E_n$ $(n\in\mathbb N)$. Define $A$ to be the set $\{a_n:n\in\mathbb N\}$, where the numbers $a_n$ are defined by induction on $n$ as follows: $a_0$ is the second element of $E_0$. $a_{n+1}$ is the second element $>a_n!!!$ in $E_{n+1}$. Then $A$ is bi-immune, because, for all $n$, $A\cap E_n$ contains $a_n$ while $\overline A\cap E_n$ contains the first element $>a_{n-1}!!!$ in $E_n$ (or, when $n=0$, the first element of $E_0$).
Because of the huge gaps between the $a_n$'s, nothing about this $A$ looks random to me.
A: Suppose $X$ is bi-immune and $f:\mathbb{N}\rightarrow\mathbb{N}$ is a strictly increasing computable function. Define sets $I_n$ as follows:

*

*$I_0=[0,f(0)]$.


*$I_{n+1}=(f(n), f(n+1)]$.
Now let $$X_f=\bigcup_{n\in X}I_n.$$ The set $X_f$ is also bi-immune, but by picking $f$ appropriately we can make $X_f$ look very far from random in any sense I can think of. So not only (per Andreas) can we construct some bi-immune set which is "far from random," we have a uniform procedure for constructing, given any bi-immune set, such an "unrandom" bi-immune set which is very similar to it (e.g. in the same $m$-degree).
