Incompressibility results

1 dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus

Revision of the topics of previous letter as a motivation for proving that if x=ywz is not compressible then neither of the 3 is compressible by log terms.
Proof of C(<x,y>) <= C(x) + C(y) +O(log min{C(x),c(y)} and its refinements.
Discussion on Language compression theorem.
Statement and initial consideration about symmetry of information. Its connection to information theory.