[proofplan] We use the computability of $X$ to build a uniformly computably enumerable sequence of open sets that captures $X$ at every level. At stage $n$, take the cylinder determined by the first $n$ bits of $X$; this cylinder has product measure exactly $2^{-n}$. These cylinders form a Martin-Löf test, and since $X$ belongs to all of them, $X$ fails the test and therefore is not Martin-Löf random. [/proofplan] [step:Define the cylinder test from the computable prefixes of $X$] Since $X \in 2^{\mathbb{N}}$ is computable, there is a total computable map \begin{align*} f: \mathbb{N} &\to \{0,1\} \\ i &\mapsto X_i \end{align*} which computes the $i$th bit of $X$. For each $n \in \mathbb{N}$, define the finite binary string $\sigma_n \in 2^{<\mathbb{N}}$ of length $n$ by \begin{align*} (\sigma_n)_i := f(i) \end{align*} for $1 \leq i \leq n$. Define the [open set](/page/Open%20Set) $U_n \subset 2^{\mathbb{N}}$ by \begin{align*} U_n := [\sigma_n]. \end{align*} Because $f$ is computable, the map $n \mapsto \sigma_n$ is computable. Hence the sequence $(U_n)_{n \in \mathbb{N}}$ is uniformly computably enumerable open: an algorithm, given $n$, enumerates the single basic cylinder $[\sigma_n]$. [guided] The point of computability is that we can effectively describe longer and longer initial segments of $X$. Since $X$ is computable, there is a total computable map \begin{align*} f: \mathbb{N} &\to \{0,1\} \\ i &\mapsto X_i \end{align*} which outputs the $i$th bit of $X$. For each $n \in \mathbb{N}$, we package the first $n$ computed bits into a finite binary string $\sigma_n \in 2^{<\mathbb{N}}$ by setting \begin{align*} (\sigma_n)_i := f(i) \end{align*} for every $1 \leq i \leq n$. This is an effective construction: given $n$, compute $f(1), \dots, f(n)$ and write down the resulting finite string. Now define \begin{align*} U_n := [\sigma_n] \subset 2^{\mathbb{N}}. \end{align*} The set $U_n$ is open because it is a basic cylinder in Cantor space. Moreover the sequence $(U_n)_{n \in \mathbb{N}}$ is uniformly computably enumerable open: one algorithm takes input $n$, computes $\sigma_n$, and enumerates the single cylinder $[\sigma_n]$. This is exactly the effectiveness requirement needed for a Martin-Löf test. [/guided] [/step] [step:Verify the Martin-Löf measure bound] For each $n \in \mathbb{N}$, the string $\sigma_n$ has length $n$. By the defining property of the product probability measure $\mu$ on $2^{\mathbb{N}}$, \begin{align*} \mu(U_n) = \mu([\sigma_n]) = 2^{-|\sigma_n|} = 2^{-n}. \end{align*} Therefore $(U_n)_{n \in \mathbb{N}}$ is a Martin-Löf test. [/step] [step:Show that $X$ is captured by every level of the test] Fix $n \in \mathbb{N}$. For every $1 \leq i \leq n$, the definition of $\sigma_n$ gives \begin{align*} (\sigma_n)_i = f(i) = X_i. \end{align*} Thus $X$ has prefix $\sigma_n$, so $X \in [\sigma_n] = U_n$. Since this holds for every $n \in \mathbb{N}$, \begin{align*} X \in \bigcap_{n=1}^{\infty} U_n. \end{align*} By definition, a Martin-Löf random sequence avoids every Martin-Löf test, meaning it is not contained in the intersection of the test levels. The sequence $X$ is contained in the intersection of the Martin-Löf test $(U_n)_{n \in \mathbb{N}}$, so $X$ is not Martin-Löf random. [/step]