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(<math>\sqrt N</math>) complexity, an approach "...further improved by a Scottish farmer named O. McDonald" (priority disputed).
More ingenious approaches yield songs of complexity O(<math>\log N</math>). Finally, progress during the 20th 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
- <math>S_0=e, S_k = V_kS_{k-1},\, k\ge 1,</math>
- <math>V_k =</math> 'That's the way,' <math>U</math> 'I like it,' <math>U</math>, for all <math> k > 0</math>
- <math>U=</math> 'uh huh, uh huh'
[edit] References
- Knuth, D. The Complexity of Songs, SIGACT News, Summer 1977, 17-24.
- Knuth, D. The Complexity of Songs, Communications of the ACM, 1984, 27 (4) pp. 345--348.
[edit] External links
- The Complexity of Songs, Knuth, Donald E. (1984). (pdf)
- I MAY NOT HAVE ENOUGH OF ME BUT I'VE HAD ENOUGH OF YOU A real song from 1979, with "recursive" lyrics.
