%\subsection{Kolmogorov Complexity}

\label{s:kolmogorov}
Kolmogorov complexity, also known as Algorithmic Information Theory, was
founded in the 1960s by R. Solomonoff, G. Chaitin, and A.N. Kolmogorov.
We shall only make use of some basic facts; for a more thorough
introduction the survey article \cite{Li:HTCS:1990} or the book
\cite{Li:1997} are recommended.  The central idea is simple: measure
the `complexity' of an object by the length of the smallest program that
generates it.  This generalizes to the study of \emph{description
systems}, that is, systems by which we define or describe objects,
of which programming languages, logics, and descriptive set theory
are prominent examples.
The source code of a program, for example, describes a program behaviour;
a set of axioms describes a class of mathematical structures.  In the
general case we have some objects we wish to describe, and a
description system $\phi$ that maps from a description $w$ (for us,
a program) to objects.
% \editor{This is inconsistent with the notation
% $\phi_p(y)$; maybe use $\phi(p,y)$.}
The usual situation is to describe an object by exhibiting a
program that generates it; in this case we may also provide some inputs
to the program, which we shall call \emph{parameters}.  The Kolmogorov
complexity of an object $x$ in the description system $\phi$, relative
to a parameter $y$ is defined by:
\begin{align}
C_\phi(x ~|~ y) = \min_w \{ \strlen{w} : \phi_w(y) = x \}  \label{eqn:relativek}
\end{align}
%In \refeqn{eqn:relativek}, $w$ ranges over all possible programs.
In the case where the description system $\phi$ is a programming language,
we may read \refeqn{eqn:relativek} as finding the shortest program that,
given input parameter $y$, outputs $x$.  The parameter $y$ does not contribute
to the measured description length $C_\phi(x ~|~ y)$.
Without a parameter we have
the simpler case $C_\phi(x) = C_\phi(x ~|~ \epsilon)$ where $\epsilon$
is the empty string.

For example, we might choose the programming language Java as our
description system; then for some string $x$, its Kolmogorov complexity
$C_\mathsf{Java}(x)$ is the length of the shortest program that outputs 
$x$.
To determine whether use of a library $\mathsf{L}$ offers a reduction in
program size, we can consider the combination of Java and the library
$\mathsf{L}$ as a description system itself which we might call
$\mathsf{Java}+\mathsf{L}$, and
compare $C_\mathsf{Java + L}(x)$ to $C_\mathsf{Java}(x)$.

A very useful insight is that the choice of language doesn't
much matter.

\begin{fact}[Invariance {\cite[\S 2.1]{Li:1997}}]
\label{fact:invariance}
There exists a universal machine $U$ such that
if $\phi$ is some
effective description system (e.g., a programming language)
then there is a constant $c$ such that $C_U(x) \leq C_\phi(x) + c$ for any $x$.
\end{fact}
That is, the universal machine $U$ is optimal up to a constant factor.
For this reason the subscript $U$
can be dropped and one can write $C(x)$ for the Kolmogorov
complexity of $x$, knowing it is only defined up to some constant
factor.\footnote{There is an easy way to see why this is true:
if $\phi$ is a programming language, then we can write a
$\phi$-interpreter for the universal machine $U$.  We can
then take any program for $\phi$, prepend the interpreter,
and it becomes a $U$-program.  The constant mentioned reflects
the size of such an interpreter.}

Some strings have very short descriptions: a string of a trillion
zeros may be produced by a short program.  Others require descriptions
as long as the strings themselves, for instance a million digit
binary string obtained from a physical random bit generation device.\footnote{
Unless you are rather lucky.}
% Objects whose shortest description is not smaller than the object itself 
% are called \emph{incompressible} or \emph{Kolmogorov random}.  
A recurrent theme in
Kolmogorov complexity is that there are never enough descriptions
to go around so as to give short descriptions to most objects.  
In the case where both the objects and their descriptions are binary
strings, we have the following well-known result that the probability
we can save more than a constant number of bits in compressing 
randomly selected strings is zero.
\begin{fact}[Incompressibility {\cite[\S 2.2]{Li:1997}}]
\label{fact:incompressibility}
Suppose $g : \N \rightarrow \N$ is an integer function with $g(n) > 0$ and
$g \in \omega(1)$,
that is, $\lim_{n \rightarrow \infty} g(n) = \infty$.
Let $x$ be a string chosen \emph{uniformly at random}.
Then almost surely:
\begin{align}
C_\phi(x) \geq \strlen{x} - g\bigl(\strlen{x}\bigr) \label{e:incompressibility}
\end{align}
\end{fact}
% The $K(x) \geq |x| - \log |x|$ version is for prefix complexity; see
% p. 202 of Li and Vitanyi.

% Kolmogorov complexity coincides more-or-less with the information-theory version
% when $\Hdomain=1$, i.e., there is a uniform distribution on programs. 
\reffact{fact:incompressibility} implies, for example, that one cannot 
devise a coding system that
compresses strings by even $\log \log n$ or $\alpha^{-1}(n,n)$ 
(inverse Ackermann) bits with nonzero probability.
The proof of \reffact{fact:incompressibility} uses counting arguments
only, with no appeal to computability of the description
system.\footnote{
There are $2^{n-g(n)+1}-1$ descriptions of length
at most $n-g(n)$, and $2^{n+1}-1$ strings of length at most $n$.
Therefore the fraction of strings compressible by $g(n)$ bits is at most 
$\frac{2^{n-g(n)+1}-1}{2^{n+1}-1}$,
which behaves in the limit as $2^{-g(n)}$.
If $g \in w(1)$ this value vanishes as $n \rightarrow \infty$,
so $C_\phi(x) \geq \strlen{x} - g(\strlen{x})$ almost surely.
}
Therefore the inequality (\ref{e:incompressibility}) applies to
\emph{any} description system $\phi$, even description systems
that are not computable.  For example, \reffact{fact:incompressibility}
even applies if we permit ourselves to use an infinite, not computably enumerable
library as we described in \refsec{s:platonic}.
However, it does not apply in the case where there is a nonuniform
distribution, as in problem domains where $H < 1$.
% \footnote{This would be terrible
% news for software reuse were it the final word.  However, there is more to this
% story yet to come.}

In the remainder of this paper we shall assume
compiled programs are incompressible in the sense of
\reffact{fact:incompressibility}.

\begin{prop}
\label{prop:programsincomp}
Compiled C programs on existing major architectures are almost surely
Kolmogorov incompressible.
\end{prop}

Note that ``almost surely \emph{Kolmogorov}
incompressible'' does not imply anything
about the compressibility of \emph{typical} compiled programs for
a problem domain.  Rather, it means that if one
chooses a valid compiled program uniformly at random, with probability 1
it cannot be replaced by a shorter program with the same behaviour.
In subsequent sections we investigate problem domains where
there \emph{is} a nonuniform distribution on programs,
i.e., $\Hdomain < 1$, where the situation is rosier.

We sketch a proof of \refprop{prop:programsincomp}, showing that the
number of distinct behaviours described by compiled programs of $s$ bits
grows as $\sim 2^s$ on current machines, which implies compiled programs are 
almost surely (Kolmogorov) incompressible.
The C
language has the useful ability to incorporate chunks of binary
data in a program.  For example, the binary string $z = 01101001 11011010$
may be encoded by the C declaration
\begin{align*}
\mathsf{unsigned}~\mathsf{char}~\mathsf{z}[2] = \{ \mathsf{0x69}, \mathsf{0xda} \};
\end{align*}
\noindent
Moreover, such arrays are laid out as contiguous binary data in the
compiled program, so that a binary string of length $m$ bytes requires
exactly $m$ bytes in the compiled program.  
We can package such an
array with a short program of constant size that reads the
binary string from memory and outputs it to the console. 
Every binary string of $m$ bytes may be encoded by such a compiled
program of size at most $c + m$ bytes, where $c$ is a constant 
representing the overhead of a read-print loop.  Every such program
yields a unique behaviour, so the number of distinct behaviours of
compiled programs of $s$ bits is $\sim 2^s$.
We can then adapt the argument used to prove
\reffact{fact:incompressibility}, replacing strings by compiled programs,
which shows compiled C programs are almost surely incompressible.

% \editor{The proof of \reffact{fact:incompressibility} uses a
% strict counting, but here we have an asymptotic $\sim 2^n$.
% Better explain this more carefully.}

Note that uncompiled programs are \emph{highly} compressible.
For example, C language source code may not contain certain bytes
(e.g., control characters) such as the null character $0x00$.
This means they can be compressed by a factor of 
(at least) $\frac{1}{256} \sim 0.39\%$.
Restricting our attention to \emph{compiled}
programs is crucial.\footnote{An alternative would be to
deal with \emph{indices} of programs in the usual sense
of computability theory, where we equate a program with its
position in some effective enumeration of valid source-language
programs.
However, working with compiled programs has the additional benefit
of brushing aside issues such as identifier lengths in
source code, which tend to be unnecessarily long to
aid readability.
}

