### Sumários

##### Prefix-free Kolmogorov complexity

15 Dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus

Motivation for prefix-free Kolmogorov complexity. Definition of prefix-free Kolmogorov complexity and its properties. Prefix-free Kolmogorov complexity and probability distributions. Three different approaches and the the Coding theorem. Application to Information theory.

Lecturer: Andre Souto.

##### Symmetry of Information

10 Dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus

Considerations about mutual information a la Kolmogorov complexity. Proof that symmetry of information cannot hold up to constant terms. Statement and proof of symmetry of information with logarithmic terms. Digression to application on security.

##### There were no classes

3 Dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus

There were no classes.

##### 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.

##### The Kolmogorov-Solomonoff theorem of invariance

26 Novembro 2015, 14:00 • Paulo Alexandre Carreira Mateus

The Kolmogorov-Solomonoff theorem of invariance. Examples of application.Upper bounds on Kolmogorov complexity. The incomputability theorem. Incompressibility theorem.