Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
“2-randomness and complexity”
We will begin our proof that Z is 2-random if and only infinitely many of its initial segments are incompressible in the sense of plain complexity.
We will start by sketching the weaker implications obtained by relaxing 2-randomness to 3-randomness and 1-randomness. These results give a good idea of the proof strategy used to prove the full theorem.
We will then introduce compression functions, which may be thought of as noncomputable analogues of complexity, and which are the main idea used to move from the simpler results mentioned above toward a proof of the full theorem.
MC 5403