Is Kolmogorov-Complexity only for constant output?

Question

We have lot's of challenges that are about producing constant output. For example:

• We're no strangers to code golf, you know the rules, and so do I

• Print a 10 by 10 grid of asterisks

• Every single one of the "alphabet challenges" we've been recently flooded with

These are very clearly kolmogorov-complexity questions, since Kolmogorov-Complexity is

Kolmogorov complexity, informally, is the amount of code it takes to produce a given string of text

However, there are a lot of challenges (generally ascii-art challenges) that are about producing a given string of text depending on the input. For example:

• Build a triangle without any triangles

• Turtles All the Way Down

• The IHIH Pyramid

• Quack the Angry Duck

• Many many many others

All of these are not pure KC questions, since the output varies. However, they are all tagged with KC also. Should they be tagged any differently since the output is not constant? Is it worth making a distinction between constant-kolmogorov-complexity and varied-kolmogorov-complexity? (Obviously we could come up with a better name if we decide to retag)

Answer 1

The kolmogorov-complexity tag was initially applied only to what you might term pure Kolmogorov complexity questions: those which asked for a constant output. Its scope has expanded over time, and I have also felt that its application to some questions was overbroadening it. However, to limit it to constant-output questions would be to overnarrow it.

Definition

A couple of quotes from Wikipedia (my emphasis):

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output.

The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity

To restrict the tag to constant-output questions (understanding output to mean strings or byte sequences, since writing to stdout is one of our standard output options) is to discard other objects. And to insist on the narrowest possible definition of the term KC is to put pedantry ahead of the value and purpose of the tag system, which is to enable people to find questions of interest to them.

An example

IIRC one of the earliest non-constant-output questions to be tagged kolmogorov-complexity (and it turns out that I was the one who tagged it, although I didn't remember that when I went looking for it yesterday) was Who's that Pokémon? It takes one input, an integer, and gives one string as output. There's no mathematical formula^[1] which will get the output from the input.

This question could have been written as follows:

Write a function (not a program) which takes no input and returns an array of these 151 elements in this order: ...

Is there any good argument that this rewrite doesn't deserve kolmogorov-complexity? Sure, it's a function rather than a program, but that's only because a program can't output an array but only a string representation of an array.

Or can it? By taking the array index as an input and giving the corresponding element as an output, answers to the question as written are essentially managing to output an array to stdout. So although on a very narrow definition this question might not be KC, there's a strong argument that it's actually asking for the KC of a non-text object even on a fairly narrow definition, and I don't think it's possible reasonably to argue that it doesn't fall within the "broader area encompassing descriptional complexity" mentioned in the second Wikipedia quote.

^[1] Ok, you pedants, except a case-wise definition.

Answer 2

Kolmogorov complexity is specifically the length of a program (in a given language) that produces the given constant string as output. Note the constant - there is no mention in Kolmogorov complexity theory of non-constant strings (producing one of multiple outputs based on an input parameter). In other words, there is no input.

KC-like challenges which require outputting a string based on an input parameter have nothing to do with Kolmogorov complexity, and should not be tagged as such.

Answer 3

Edit the tag wiki

Personally I feel that Kolmogorov complexity can be extended apply to any string output which has a clear pattern which can be exploited to increase brevity. The tag wiki should be modified to reflect this.

However, Strings with a very high complexity like ("Hello, World!") are certainly not excluded from this tag wiki as DJMcMayhem pointed out. KC should continue to reflect challenges which have a high complexity and may lack tricks to golfing it down. (However most such challenges should be avoided)

This consensus has been shown in multiple questions, and that is why I suggest it. Please vote up/down this proposal however you see fit.