Information

The Church-Turing thesis gives a universally applicable definition of algorithm, but we don’t have an equivalently comprehensive definition of information

To start with an example,
$A=1010101010101010$
$B=1110101001011010$

Intuitively, $A$ contains less information than $B$ because it’s more repetitive

Our idea is that the length of an object’s shortest possible description is a measure of its information

We restrict our attention to binary strings and binary descriptions, and then look at what kinds of descriptions we may allow

Definition: The minimal description $d(x)$ of a binary string $x$ is the lexicographically first shortest string $⟨M,w⟩$ where TM $M$ on input $w$ halts with $x$ on its tape

The descriptive complexity of $x$ is $K(x)=|d(x)|$

This definition amounts to measuring the possible compression of $x$

Theorem: $\exists c\forall x[K(x)\le |x|+c]$
We can always use the identity Turing machine to create a description of $x$

Theorem: $\exists c\forall x[K(xx)\le K(x)+c]$

We can construct a Turing machine $M=$ “On input $⟨N,w⟩$, run $N$ on $w$ until it halts and produces $s$, and then output $ss$”

A description of $xx$ is then $⟨M⟩d(x)$, and its length is $|⟨M⟩|+|d(x)|=c+K(x)$

Theorem: $\neg \exists c\forall x,y[K(xy)\le K(x)+K(y)+c]$, i.e. concatenating strings leads to a greater bound than $K(x)+K(y)+c$

To prove this theorem, we must show that for any $c$ there is some $x$ and $y$ where $K(xy)>K(x)+K(y)+c$

The book leaves this as an exercise :/

Definition: Consider a description language to be any computable function $p:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ and define the minimal description of $x$ with respect to $p$, written $d_p(x)$, as the first string $s$ where $p(s)=x$ in standard string order, with $K_p(x)=|d_p(x)|$

Theorem: For any description language $p$, a fixed constant $c$ exists where $\forall x[K(x)\le K_p(x)+c]$, i.e. our Turing machine definition of descriptive complexity is reasonably optimal

This seems impressive but the proof is trivial, since we can define $M=$ “On input $w$: Output $p(w)$” and its length is at most $⟨M⟩$ greater than $K_p(x)$

Definition: $x$ is c-compressible if $K(x)\le |x|-c$, otherwise $x$ is incompressible by c, and if $c=1$ then $x$ is incompressible

Theorem: Incompressible strings of every length exist

The number of binary strings of length $n$ is $2^n$ and the number of descriptions of length less than $n$ is ${\sum }_{0\le i<n-1}^{}{2}^i=2^n-1$, so there is at least one incompressible string of length $n$

Corollary: At least $2^n-2^{n-c+1}+1$ strings of length $n$ are incompressible by $c$

This follows from the same logic

Incompressible strings have many properties we’d expect in randomly chosen strings, such as a roughly equal number of 0s and 1s and a longest run length of about ${\log }_{2}n$

We can prove something even more general

A property of strings is a function $f$ that maps strings to $\{\text{TRUE},\text{FALSE}\}$ and a property holds for almost all strings if the fraction of strings of length $n$ on which it is $\text{FALSE}$ approaches 0 as $n$ grows

Theorem: Let $f$ be a computable property that holds for almost all strings, then for any $b>0$, the property $f$ is $\text{FALSE}$ on only finite many strings that are incompressible by $b$

$M=$ “On input $i$, find the $i$th string $s$ where $f(s)=\text{FALSE}$ and output $s$”

For any such string $x$, let $i_x$ be the position or index of $x$ on a list of all strings that fail to have property $f$, in which case $⟨M,i_x⟩$ is a short description of $x$ with length $|i_x|+c$

For any $b>0$, select $n$ such that at most a $1/2^{b+c+1}$ fraction of strings of length $n$ or less fail to satisfy $f$

Let $x$ be a string of length $n$ that fails to have property $f$
$i_x\le \frac{2^{n+1}-1}{2^{b+c+1}}\le 2^{n-b-c}$
$|i_x|\le n-b-c$, so $K(x)\le n-b$
Thus every sufficiently long $x$ that fails to satisfy $f$ by virtue is compressible by $b$ and our theorem follows

Unfortunately, this is all confined to theory because $K(x)$ is not computable, no algorithm can decide in general if a string is incompressible, and there is not even an infinite subset of Turing-recognizable incompressible strings

Theorem: For some constant $b$, for every $x$, the minimal description $d(x)$ is incompressible by $b$

To prove this, consider $M=$ “On $⟨R,y⟩$, run $R$ on $y$ and reject if the output is not of form $⟨S,z⟩$. Run $S$ on $z$ and halt with its output on the tape.”

Let $b=|⟨M⟩|+1$ and suppose $d(x)$ is $b$-compressible for some string $x$
This means $|d(d(x))|\le |d(x)|-b$
But then $⟨M⟩d(d(x))$ is a description of $x$ with length $|⟨M⟩|+|d(d(x))|\le (b-1)+(|d(x)|-b)=|d(x)|-1$, which is a contradiction