Computably enumerable sets are not algorithmically random

Question

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would like know an elementary proof for the fact.

Thank you for your help in this matter.

Answer 1

Let $S$ be a recursive enumerable set.

• if $S$ is finite, it can't be random
• if $S$ is infinite, by definition of "recursive enumerable" there is an injective total program $p: \mathbb N\rightarrow S$. You can use $p$ to build your constructive null cover. Let $s(i)=\max_{k\le i}p(k)$. Consider the set of finite binary words $W_i$ such that $$W_i=\{w\;|\; (\forall k\le i :w_{p(k)}=1)\wedge(|w|=s(i))\}$$ and let $U_i$ a sequence of open sets such that ($C_w$ is the cylinder defined by $w$) $$U_i=\bigcup_{w\in W_i}C_{w}$$

Then $U_i$ defines a constructive null cover that contains $S$.