The Complexity of Songs

From Wikipedia, the free encyclopedia

"The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory. The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.

With a grain of truth, Knuth writes that "...our ancient ancestors invented the concept of refrain" to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one's memory. Knuth's Lemma 1 states that if N is the length of a song, then the refrain decreases the song complexity to cN, where c < 1.

Knuth further demonstrates a way of producing songs with O(\sqrt N) complexity, an approach "...further improved by a Scottish farmer named O. McDonald" (priority disputed).

More ingenious approaches yield songs of complexity O(logN). Finally, progress during the twentieth century—stimulated by the fact that "the advent of modern drugs has led to demands for still less memory"—leads to the ultimate improvement: Arbitrarily long songs with space complexity O(1), e.g. for a song to be defined by the recurrence relation

S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,
Vk = 'That's the way,' U 'I like it,' U, for all k > 0
U = 'uh huh, uh huh'

[edit] References

[edit] External links