The generalized probability coding conjecture for PGP^G

At least 25 years old · documented by

Let B♯B^{\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 x∈B♯x\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.