The enumerable probability coding conjecture for PEP^E

From papers

Let BB^{\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 xBx\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.

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.