This appendix represents a formal equivalent of the basic concepts discussed in the article.

Each Turing machine (TM) *C*
(mapping bitstrings to bitstrings,
without loss of generality)
computes a partial function
*f*_{C}
: {0,1}* -> {0,1}*.
(*f*_{C} is undefined where *C* does not halt).

**Compiler theorem.**
There is a universal TM *U* with the
following property:
for every TM *C* there exists a constant prefix
mu_C (a bitstring)
such that
*f*_{C}
(p)=
*f*_{U}
(mu_C p)
for all bitstrings *p*. mu_C
is the compiler that compiles programs for *C* into
equivalent programs for *U*.

**Kolmogorov complexity.**
The Kolmogorov complexity
*K*_{U}(*s*)
of a finite string *s* is
the length of the shortest
program *p* that computes *s* on a universal
Turing machine *U* and halts,
where the set of possible halting programs forms a prefix code
(no halting program can be the prefix of another one):
*K*_{U}(*s*)
=
*min*_{p}
{| p | :
*f*_{U}
(p)
= s},
where
| p |
denotes the length of *p*.
In general, *K*_{U}(*s*) is noncomputable.

**Invariance theorem**.
Due to the compiler theorem,
*K*_{U1}(*s*) = *K*_{U2}(*s*) + *O*(1) for two universal machines
*U*_{1} and *U*_{2}.
We choose one particular
universal machine *U* and write
*K*(*s*) = *K*_{U}(*s*).

Back to Theory of Beauty page

Back to Algorithmic Information page