Computability Learning Seminar

After we have established the machine existence (Kraft-Chaitin Theorem), this time we are going to give the proofs for the following "desirable" facts about $K$ which we stated before: (a) Incompressible (in the sense of $K$) strings have only short runs of zeros (i.e. blocks only consisting of zeros), and (b) Zeros and ones occur balancedly.

 

MC 5403