Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.


Given any $S\subseteq \mathbb{N}$ we define maps $\mu\_S^+, \mu\_S^-:{\cal P}(\mathbb{N})\to[0,1]$ by setting, for every $A\in{\cal P}(\mathbb{N})$, $$\mu^{+}\_S(A)= \lim \sup\_{n\to\infty}\frac{|A\cap S \cap\{1,\ldots,n\}|}{1+|S\cap \{1,\ldots,n\}|}, \text{ and } \mu^{-}\_S(A)= \lim \inf\_{n\to\infty}\frac{|A\cap S \cap\{1,\ldots,n\}|}{1+|S\cap \{1,\ldots,n\}|}.$$


We say that $A$ is *well-balanced* with respect to $S$ if $\mu^+\_S(A) = \mu^-\_S(A) = 1/2$.


We say that $A\subseteq \mathbb{N}$ is *computationally random* if for every [computable](https://en.wikipedia.org/wiki/Recursive_set) set $S\subseteq\mathbb{N}$, the set $A$ is well-balanced with respect to $S$. Morevover, we say that the bitstream $s:\mathbb{N}\to\{0,1\}$ is computationally random if $s^{-1}(\{1\})$ is computationally random.


Note that neither the [Thue-Morse sequence](https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence) or the [Champernowne sequence $C\_2$](https://en.wikipedia.org/wiki/Champernowne_constant) are computationally random.


**Question.** Is every computationally random bitstream normal (that is, every finite $01$-string appears infinitely often)?



Computationally random bitstreams and normalcy
Let $s$ be a computationally random bitstring. Consider $\tilde{s}$
defined by $\tilde{s}(2n) = \tilde{s}(2n+1) = s(n)$. Then $\tilde{s}$ should also be computationally random, but it does not contain any $010$ or $101$.


