Binary string ($\{0,1{\}}^{<\omega }$)

A binary string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

A self-delimiting code permits a decoder to identify the end of a code without an external length marker. Encoding a binary word of length $\ell$ by $\ell$ ones, a zero and the word uses $2\ell +1$ bits. This yields an $O(\log n)$ description of a natural number in an incompressibility proof.