5 msΒ·
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
by lgdw 3y ago
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 3y agoWhen 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|..