The enumerable probability coding conjecture for PEP^E

About 26 years old · traced to

Let B♯B^{\sharp} be the domain of finite binary strings under consideration, and let PE(x)P^E(x) and KE(x)K^E(x) denote the corresponding enumerable measure and complexity functions. Write KPE(x)KP^E(x) for the prefix complexity associated with PEP^E. Enumerable probability coding conjecture. For every x∈B♯x\in B^{\sharp} with PE(x)>0P^E(x)>0,

KE(x)≤KPE(x)+O(1).K^E(x)\leq KP^E(x)+O(1).

This conjecture proposes removing the small correction term from the corresponding coding bound for the enumerable probability. It is motivated by the discussion of tighter bounds and remains 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.