A formal definition of complexity

23 marzo 2017
March 23, 2017
Contatti: 
Staff Dipartimento di Matematica

Università degli Studi Trento
38123 Povo (TN)
Tel +39 04 61/281508-1625-1701-3898-1980.
dept.math [at] unitn.it

Venue:  Seminar Room “-1” – Department of Mathematics
Time: 12:00

  • Speaker: Manlio Valenti

Abstract: While the notion of complexity is somewhat intuitive, it is not trivial to define it formally. A possible solution is the one suggested by Kolmogorov, who exploited the framework of computability  theory to define a function that "measures the complexity" of a string.
This function, despite the fact that it is incomputable, matches the intuitive idea of complexity in many ways. The notion of Kolmogorov complexity marks the beginning of the branch of mathematics called  Algorithmic Information Theory. We will also discuss the relation between Kolmogorov complexity and probability theory and how we can  address the problem of sequence prediction in this context.

Contact person: Claudio Agostinelli

Download