Why Oatmeal Is Cheap: Kolmogorov Complexity and Procedural Generation[pdf]

Re:Why Oatmeal Is Cheap: Kolmogorov Complexity and Procedura... by lgdw on Saturday April 29, 2023 @03:52AM (#35750976)

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)...

[ Parent | on HN ]

Re:Why Oatmeal Is Cheap: Kolmogorov Complexity and Procedura... by srcreigh on Saturday April 29, 2023 @08:08AM (#35752156)

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|..

[ Parent | on HN ]