3 ms·
> It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description
by jnape 11y ago
> It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description language.
If you don't find it fitting to describe an implementation of an algorithm as an expression of that algorithm, fair enough.
> This confusion between the Kolmogorov complexity of a string and the Kolmogorov complexity of an algorithm [1] haunts the entire article.
"The Kolmogorov complexity of an algorithm" was intended to be "the Kolmogorov complexity of the implementation of an algorithm in some language by some engineer", but perhaps the entire article is rendered ineffective due to this lack of clear distinction. I'll accept that.
> Saying "extrinsically identical algorithms" makes it unclear whether the author understands the difference between an algorithm and a function.
Perhaps I was too lazy and should have said "extrinsically identical _implementations_ of some algorithm". It is true that algorithms are by most definitions (I like Turing's) necessarily more abstract than the computational mechanisms we use to reify them, but it didn't seem like a crucial failure to not be pedantic about this distinction. Perhaps it was.
Hopefully subsequent articles will benefit from your points. Thanks very much for the feedback!
- j2kun 11y agoI think you may be still seriously confused by the definition of Kolmogorov complexity. It's not a fine distinction I'm trying to make, but rather that your definition has a type error! You should think hard about how Kolmogorov complexity (which is defined for strings) can make sense when you try to extend the definition to algorithms in the way you want. They way you've done it is not consistent from what you've written. I suggest you read a few more tutorials on Kolmogorov complexity.