I currently have a few ideas for questions involving kolmogorov complexity, mostly how to output song lyrics in the shortest method (example: Diggy Diggy Hole by the Yogscast, http://yogscast.wikia.com/wiki/Diggy_Diggy_Hole_(Song), mainly because I've had it stuck in my head since the day of release), But I've got the feeling that questions that are purely KGC, with no other limitations, are, wel, not complex enough.

Am I right in feeling that these questions would be somewhat bland? I'm thinking that a possible option might be that the program should follow the rythm of a part of the song, or that you cannot use any characters from the artist's name and 2 key words to the song (in this case Yogscast, Dwarves and Goblins).

Or is there not really a way to save such simple kolmogorov complexity questions?

  • \$\begingroup\$ I suppose it's less a problem that pure kolmogorov challenges can't be done but rather that they have been done already. I suppose a simple "write the shortest code to output these lyrics" would be closed as an indirect duplicate of some of the simpler existing kolmogorov challenges. This could be solved by either making it a [restricted-source] challenge with a novel restriction as you suggest or by picking a target output which contains an unusual form or symmetry/repetition which requires/allows new methods for compressing the code. \$\endgroup\$ Aug 18, 2014 at 9:47
  • \$\begingroup\$ As an example for the latter, kolmogorov challenges where you piece together an ASCII art output from several blocks has been done before (see here and here), but I figure my recent challenge added something to the mix because it contained both rotational and mirror symmetries as well as introducing overlap of the blocks that are to be glued together. \$\endgroup\$ Aug 18, 2014 at 9:50


You must log in to answer this question.

Browse other questions tagged .