Tag proposal: kolmogorov-complexity

Question

The Kolmogorov complexity of a string is the size of the smallest code fragment that produces it. Kolmogorov complexity is undecidable and infeasible to compute.

Code golfing is the task of implementing something in the fewest characters possible, and in general is very much like approximating Kolmogorov complexity. Some posts, like Calculate 500 digits of pi, Mixed up output., and 99 Bottles Of Beer ask you to produce a string, usually with the smallest program possible.

I'm proposing a new tag, kolmogorov-complexity, for questions that, ideally, have these conditions:

• Goal is shortest length (i.e. code golf).
• Code is expected to output a given string exactly.
• The string will preferably have non-obvious and unknown patterns. The challenge of Kolmogorov complexity is mainly to find those patterns.
• The string must not be purely random.

Not a lot of questions follow this template exactly, and most probably shouldn't be given the kolmogorov-complexity tag. "Calculate 500 digits of pi" fits this tag very well, whereas "99 Bottles of Beer" does not, as it asks for "creative use of a language" rather than shortest code length.

Before I go on a tagging vendetta, I'd like some input on this.

Answer 1

Sounds good to me.

As I've said we should encourage pretty free and descriptive tagging for the time being, and kolmogorov-complexity represents a recognizable category of problems.