[lgdw]

Having a hard time following the lower bound proof, especially this part:

> By the definition of 𝑃𝑎 , we know there are at least as many programs in 𝑃𝑎 as there are artefacts in 𝜋 (𝐺), i.e. |𝑝𝑎 | ≥ #𝜋 (𝐺).

I'm not sure how the definition of P_a leads to |p_a| >= #\pi(G)...

[srcreigh]

When they say P_a, they must mean all the minimal programs for every artifact generated by G. It’s like the union of p_a over all the artifacts.

P_a definitely can’t be all the maximally compressed programs for specific a. There’s at most 2^|p_a| of them and if G were the identity function on m length binary strings where m>|p_a|..