A universal Martin-Löf test exists

Dovetail the universal evaluation of the $e$-th partial computable function over all natural inputs and running times. Decode any output as a pair $(k,\sigma )$ and discard malformed outputs. This uniformly enumerates a c.e. relation $W_e\subseteq \mathbb{N}\times \{0,1{\}}^{\ast }$ for each $e$. Conversely, an enumeration program for any c.e. relation appears in the numbering Universal and acceptable numberings, so the relations $W_e$ cover every uniformly effectively open candidate sequence.

For candidate $e$, at component $k$ retain a newly enumerated cylinder only when the finite union retained so far would still have measure at most $2^{-k}$. Delete strings extending another string in the finite list; the remaining prefix-free cylinders are disjoint, so their rational measures $2^{-\mathrm{\mid }\sigma \mathrm{\mid }}$ sum to the exactly computable union measure. The retention rule is therefore uniform and c.e. Its finite retained unions have measure at most $2^{-k}$, and continuity from below Continuity from below for measures gives the same bound for their increasing union. If the candidate already is a Martin-Löf test, none of its cylinders is discarded, since every finite subunion is contained in its component of measure at most $2^{-k}$.

Let $V_n$ be the union of all retained $e$-components at level $n+e+1$. Dovetailing the enumerations makes $(V_n)$ uniformly effectively open, and countable subadditivity Finite and countable subadditivity of measures gives $\mu (V_n)\le {\sum }_e{2}^{-(n+e+1)}=2^{-n}\mathrm{.}$ It is therefore a test by Martin-Löf tests and random sequences. If $(U_k^e)$ is a genuine test, step 2.1 does not trim it, so $U_{n+e+1}^e\subseteq V_n$ for all $n$. Take $c_e=e+1$ to obtain the stated universality.