Since sentences
over any finite alphabet are encodable as bitstrings, without loss of
generality we focus on the binary alphabet .
denotes the empty string,
*B*^{*} the set of finite sequences over *B*,
the set of infinite sequences over *B*,
.
*x*,*y*,*z*,*z*^{1},*z*^{2} stand for strings in
.
If
then *xy* is the concatenation of *x* and *y* (e.g.,
if *x*=10000 and *y*=1111 then
*xy* = 100001111).
Let us order
lexicographically: if
*x* precedes *y* alphabetically (like in the example above)
then we write
or ;
if
*x* may also equal *y* then we write
or
(e.g.,
).
The context will make clear where we also identify
with
a unique nonnegative integer 1*x*
(e.g., string 0100 is represented by integer 10100 in the dyadic
system or
20=1*2^{4}+0*2^{3}+1*2^{2}+0*2^{1}+0*2^{0} in the decimal system).
Indices
*i*,*j*,*m*,*m*_{0},*m*_{1},*n*,*n*_{0},*t*,*t*_{0} range over the positive integers,
constants *c*,*c*_{0},*c*_{1} over the positive reals,
*f*,*g* denote functions mapping integers to integers,
*log* the logarithm with basis 2,
for real *r*>0.
For
,
0.*x* stands for the real number with dyadic expansion *x*
(note that
0.*x*0111....=0.*x*1=0.*x*10=0.*x*100... for ,
although
).
For ,
*l*(*x*) denotes the number of bits in *x*,
where
for
;
.
*x*_{n} is the prefix of *x* consisting of
the first *n* bits, if
,
and *x* otherwise (
).
For those
that contain at least one 0-bit,
*x*' denotes the lexicographically smallest
satisfying
(*x*' is undefined for *x* of the form
).
We write
*f*(*n*)=*O*(*g*(*n*)) if there
exists *c*,*n*_{0} such that
for all *n* > *n*_{0}.

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