# Presentation Outline
## Intro Example
Suppose you are in space and describing secret messages you saw to your friend through a phone call. The phone call is very expensive. How would you describe the following strings?

`1010101010101010101010101010101010101010` -> "10" repeated 20 times
`1001010110111101010101111101101111101110` -> read out one by one.

The first one has a "short" description, but the second one does not.
We want to formalize this idea using turing machines.

## Definition
Let $M$ be a machine that takes input $w$ and outputs $s$, then we can define Kolmogorov complexity as the length of the shortest machine that outputs $s$.
$$K_M(s) = MIN_{|w|} M(w)=s$$

## K(x) can be defined independent of the language
How?
## Complex strings cannot be generated
Now we have a definition for k(x). And we want to know, can we generate a string with at least a specific Kolmogorov complexity? Formally,

Is there a machine $M$ that takes input $n$, outputs a string $s$ such that $k(s) \ge n$?

Suppose it exists.

Then we choose some very large $n$ (e.g. $n=256|M|$), and let it output $s = M(n)$. By definition, $k(s) \ge n$, which means the generated string $s$ has no description shorter than $n=256|M|$.

But $\langle M\rangle n$ is a description for $s$, which has a length of

$$2|M|+1+log(n) = 2|M|+1+log(256|M|) = 2|M|+1+log(256)+log(|M|) \le 3|M| + 9 \le 12|M|$$

> Some notes:
> - $2|M|+1$ is for the $|M|$ leading 0s and a 1 to indicate the length of $|M|$ before the actual description of $M$
> - We also assume that $|M| \ge 1$

Now we have $12|M| > 256|M|$ which is a contradiction.

The intuition is that we can choose a large number as long as it's larger than the length of the machine plus its input, then the generated string is a contradiction.

Therefore no such machine exists.

## K(x) is uncomputable
We have seen that we cannot generate strings of a certain Kolmogorov complexity. We now ask, is there a machine that computes the Kolmogorov complexity of a string? Formally,

Is there a machine $M$ that takes input $s$, outputs $k(s)$?

Suppose we have a machine $M$ that on input $s$, outputs $n=k(s)$. Then we will show that we can implement a machine that outputs a complex string.

We do this by iterating through all strings $s \in \{\epsilon, 0, 00, 01, 10, ...\}$, and check whether its k-complexity is equal to $m$, and output the first string $s$ such that $k(s)=m$. This implements a machine that generates a complex string, which is shown above not to exist.

But how do we know this machine will terminate? Because above a certain length, strings have to be complex.

If we look at all descriptions of length at most $n-1$, we have $2^0 + 2^1 + 2^2 + ... + 2^{n-1} = 2^{n}-1$ such descriptions in total.

Now we look at all strings of length $n$, we have $2^n$ such strings. We can't have all of them with Kolmogorov complexity of less than $n$, because there are not that many machines (Use illustration). So we are guaranteed to find some strings with K-complexity greater than $n$ when we iterate around strings of length $n$.

If we look at strings of length $n+2$, we have four times as many strings, and at most 1/4 of those have descriptions shorter than $n$.

$$A = \big\{ w \ \big|\ k(w) \le n-1 \big\} $$
$$|A| \le |\big\{ M \ \big|\ |M| \le n-1 \big\}| = 2^{n}-1 < 2^{n}$$
$$B = \big\{ w \ \big|\ |w| = n+2 \big\}$$
$$|B| = |\big\{ w \ \big|\ |w| = n+2 \big\}| = 2^{n+2}$$

Then
$${|A|\over|B|} < {1 \over 4}$$

The observation is that most strings do not have short descriptions. Yet we cannot have a machine that generate such a string. However, if we randomly select a string of certain length, there is a pretty good chance that it does not have a short description.

This is related to the central question of randomized algorithm: Does randomization add computation power?

Can also compare with [[Chapter 10#Finding the median of an array]], which shows a much simpler randomized algorithm.

## K(x) $\le_m HALT_{TM}$
The above result can be used to prove that $HALT_{TM}$ is uncomputable. Suppose it is. Then we can iterate through all machines $M \in \{\epsilon, 0, 00, 01, 10, ...\}$ and all input strings $w \in \{\epsilon, 0, 00, 01, 10, ...\}$ in the order of increasing total length, and check whether that machine $M$ halts on input $w$. If it does not halt, we continue to the next pair; if it halts, we run machine $M$ on $w$, and if $M(w)=s$, output $|\langle M\rangle, w|$. This would be a machine that outputs the k-complexity of string $s$, which is shown not to exist.