[fen11]

This post argues that because most functions we encounter are primitive recursive, Primitive Kolmogorov complexity is widely applicable. I think you also need to argue that it is a meaningful notion of complexity.

PK may be very differently shaped from normal Kolmogorov complexity because you can find primitive recursive functions whose implementation in a primitive recursive programming language is arbitrarily larger than their implementation in a Turing complete programming language.

That said, I’m not sure what if anything this implies about AI.