4 ms·

I find the notion of kolmogorov complexity both interesting and potentially a bit misleading. The reason it is misleading is because of the extra implicit conte

by norir 1y ago

I find the notion of kolmogorov complexity both interesting and potentially a bit misleading. The reason it is misleading is because of the extra implicit context that is not present in the artifact but is necessary for interpretation. Sure, it is possible to write a ray tracer on a business card, but you can't write the c compiler or runtime on a business card so I don't agree that it is a business card sized concept when stripped to its essence. Now, you could take the Guy Steele "Growing a language route" and try to define a self-consistent program that defines every word that is used, but even then you will have to rely on some axioms that cannot be defined solely within the artifact. So then the question becomes what is the size of the axioms? In other words, Kolmogorov complexity does point to a real thing -- and I strongly agree that smaller generally corresponds to lower complexity given the same set of axioms -- but the deeper sense of complexity seems inherently unmeasurable to me. Or put yet another way, complexity can only measured relationally.

LegionMammal978 1y ago
Yeah, examples of 'small' interpreters (including 'small' self-interpreters) have always made me uneasy when they depend on a powerful runtime environment. E.g., in the limit, you can create a language where the 0-byte program is a self-interpreter, and all other programs are interpreted as Python or whatever. You can then point to "look how small the description is!" when it's really just sleight of hand. To put it as a hot take, bootstrapping is very overrated. Of course, every human definition will similarly hide complexity to some extent, so there's no real way to win.
tromp 1y ago
When Kolmogorov complexity is expressed directly in terms of the pure untyped lambda calculus, the oldest and simplest model of computation (except perhaps for SK combinatory logic, which is less expressive bit-for-bit), you cannot really complain of hidden complexity in the axioms. Even numbers have to be built from scratch.

by norir 1y ago

LegionMammal978 1y ago

Yeah, examples of 'small' interpreters (including 'small' self-interpreters) have always made me uneasy when they depend on a powerful runtime environment. E.g., in the limit, you can create a language where the 0-byte program is a self-interpreter, and all other programs are interpreted as Python or whatever. You can then point to "look how small the description is!" when it's really just sleight of hand. To put it as a hot take, bootstrapping is very overrated. Of course, every human definition will similarly hide complexity to some extent, so there's no real way to win.

tromp 1y ago

When Kolmogorov complexity is expressed directly in terms of the pure untyped lambda calculus, the oldest and simplest model of computation (except perhaps for SK combinatory logic, which is less expressive bit-for-bit), you cannot really complain of hidden complexity in the axioms. Even numbers have to be built from scratch.