The generalized probability coding conjecture for PGP^G

From papers

Let BB^{\sharp} be the domain of finite binary strings under consideration, and let PG(x)P^G(x) and KG(x)K^G(x) denote the corresponding generalized probability and complexity functions. Write KPG(x)KP^G(x) for the prefix complexity associated with PGP^G. Generalized probability coding conjecture. For every xBx\in B^{\sharp} with PG(x)>0P^G(x)>0,

KG(x)KPG(x)+O(1).K^G(x)\leq KP^G(x)+O(1).

This conjecture asks for the same tight coding inequality in the generalized setting, where the preceding discussion notes that PGP^G is a semimeasure rather than a measure. Its status is unresolved in the supplied source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Juergen Schmidhuber, “Algorithmic Theories of Everything”, arXiv:quant-ph/0011122 (2000).

Solutions 0

No solutions have been posted yet.