6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Is them meant to be in lieu of [code-golf], in addition to, or what? (BTW, the syntax [tag:kolmogorov-complexity] will get a tag appearance in post bodies (though it does not render in the preview).) \$\endgroup\$ Feb 20, 2011 at 14:29
  • 1
    \$\begingroup\$ @dmckee: Any post tagged kolmogorov-complexity should also be tagged code-golf. \$\endgroup\$
    – Joey Adams
    Feb 20, 2011 at 18:15

1 Answer 1

6
\$\begingroup\$

Sounds good to me.

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

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .