Relation between monotonic complexity and algorithmic probability 1/2
316 views · Published 3 February 2016 · 50:40 · Indexed 8 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Péter Gács (Boston University) Abstract: Some versions of Kolmogorov complexity are better suited than others when regarding finite sequences as starting segments of infinite sequences. Levin and Schnorr introduced monoton complexity, while Solomonoff and Levin introduced algorithmic probability, the distribution at the output of a universal monotonic machine reading a random coin-tossing input sequence. Monotonic complexity and the negative logarithm of algorithmic probability are very closely related, but can still be distinguished – as an old result of the author showed, using a game argument. The talk will survey the result and its proof, the significant improvement by Adam Day, and the open questions.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...