Kolmogorov complexity leads to a representation theorem for idempotent probabilities (σ-maxitive measures)
Владик Крейнович, Luc Longpré · ACM SIGACT News · 2005
In many application areas, it is important to consider maxitive measures (idempotent probabilities), i.e., mappings m for which m ( A ∪ B ) = max( m ( A ), m ( B )). In his papers, J. H. Lutz has used Kolmogorov complexity to show that for constructively defined sets A , one maxitive measure - fractal dimension - can be represented as m ( A ) = sup f ( x ). We show that a similar representation is possible for an arbitrary maxitive measure.