Computationally random bitstreams and normalcy

Question

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 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 or the Champernowne sequence $C_2$ are computationally random.

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

Answer 1

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