Notation

Much but not all of the notation used here is similar or identical to the one used in the standard textbook on Kolmogorov complexity by Li and Vitányi [#!LiVitanyi:97!#].

Since sentences over any finite alphabet are encodable as bitstrings, without loss of generality we focus on the binary alphabet $B=\{0,1\}$. $\lambda$ denotes the empty string, B^* the set of finite sequences over B, $B^{\infty}$ the set of infinite sequences over B, $B^{\sharp} = B^* \cup B^{\infty}$. x,y,z,z¹,z² stand for strings in $B^{\sharp}$. If $x \in B^*$ then xy is the concatenation of x and y (e.g., if x=10000 and y=1111 then xy = 100001111). Let us order $B^{\sharp}$ lexicographically: if x precedes y alphabetically (like in the example above) then we write $x \prec y$ or $y \succ x$; if x may also equal y then we write $x \preceq y$ or $y \succeq x$ (e.g., $\lambda \prec 001 \prec 010 \prec 1 \prec 1111...$). The context will make clear where we also identify $x \in B^*$ with a unique nonnegative integer 1x (e.g., string 0100 is represented by integer 10100 in the dyadic system or 20=1*2⁴+0*2³+1*2²+0*2¹+0*2⁰ in the decimal system). Indices i,j,m,m₀,m₁,n,n₀,t,t₀ range over the positive integers, constants c,c₀,c₁ over the positive reals, f,g denote functions mapping integers to integers, log the logarithm with basis 2, $lg(r) = max_k \{integer~k: 2^k \leq r \}$ for real r>0. For $x \in B^* \backslash \{ \lambda \}$, 0.x stands for the real number with dyadic expansion x (note that 0.x0111....=0.x1=0.x10=0.x100... for $x \in B^*$, although $x0111....\neq x1 \neq x10 \neq x100...$). For $x \in B^*$, l(x) denotes the number of bits in x, where $l(x)= \infty$ for $x \in B^{\infty}$; $l(\lambda) = 0$. x_n is the prefix of x consisting of the first n bits, if $l(x) \geq n$, and x otherwise ( $x_0 := \lambda$). For those $x \in B^*$ that contain at least one 0-bit, x' denotes the lexicographically smallest $y \succ x$ satisfying $l(y) \leq l(x)$ (x' is undefined for x of the form $111\ldots 1$). We write f(n)=O(g(n)) if there exists c,n₀ such that $f(n) \leq cg(n)$ for all n > n₀.

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI