Let denote python.
We say if running the python interpreter on the program outputs string .
K-complexity is a neat notion --- it’s the length of the shortest python program that prints out your string.
We’ll write for the K-complexity of a string.
Def: length of , i.e., .
Def: is random if .
Proposition:
There are random strings of every length.
Proof: count.
Cool fact 1:
is random is a statement which is often true, but rarely provable!
In particular, let be a formal system, describable in bits.
Suppose is consistent and proves that some length string is random.
Suppose we do a brute force search over proofs. Let be the first length string that we find a proof of randomness for. It must exist because proves that some string is random.
But then we have . When traditionally for random .
”In any consistent logical system, there are true statements that aren’t provable”.
Ridiculous proof of prime number theorem:
Lemma:
Let be the set of prime divisors of random numbers.
is infinite.
Proof:
Suppose were finite. Let .
Suppose we encoded numbers as follows:
We wrote down the index of the largest prime dividing them (using a prefix-free code), and then wrote down how many copies of each prime dividing them there are.
Then, random numbers of length could be specified in like bits, while they actually need bits.
Ok, now we’ll actually go all the way.
Theorem:
Proof:
Let be an ordered list of the primes.
For each , let be the smallest random number whose largest prime divisor is ; such a random number exists by the lemma.
We can encode in the following silly way:
Where is a prefix free encoding of .
This gives:
Whence,
Whence,
Letting
We have:
To extend this to the full thing that we actually care about, namely, for all ,
idk just figure it out.
Ok here’s another crazy thing.
Theorem
Let be a single tape Turing machine, with a 2way read/write head.
Suppose decides the language . Then, requires time on almost all inputs.
Proof
We assume that writes its answer in the cell after the “input end” marker.
Suppose that can handle random inputs in time .
Fix random bit number .
Try running on . There should be a location in the middle where if we write down a list of the TMs state each time it crosses that location, it’ll only take bits to describe.
We claim that this list, along with the description of and the input size gives a description of which is impossible, the description would be too short.
Ok but how to reconstruct .
Imagine running the TM on inputs of the form .
Suppose that the crossing sequence is the same as it was for .
Then, the TMs answer will be the same.
So we must have .
Thus if you give the crossing sequence, we can brute force search for .
So this is a small description of .