QED

Computerwetenschapper Donald Knuth zit nooit verlegen om een geek-grap. Zo publiceerde hij in 1977 het artikel “The Complexity of Songs” (ACM SIGACT News, Vol. 9 , No. 2, pp. 17-24 (1977)). Hierin bespreekt hij de evolutie van de structuur van populaire liedjes in de context van complexiteitstheorie. Knuth begint zijn tekst met een motivering van waarom we het refrein hebben uitgevonden:

It is known that almost all songs of length n require a text of length ~ n. But this puts a considerable space requirement on one’s memory if many songs are to be learned; hence, our ancient ancestors invented the concept of a refrain. When the song has a refrain, its space complexity can be reduced to cn, where c < 1 as shown by the following lemma.

Lemma 1 zegt dan: als S een liedje is met m verzen van lengte V en een refrein van lengte R, waarbij we het refrein als eerste en laatste zingen en tussen twee verzen, dan is de geheugencomplexiteit van S voor een vaste V en R gelijk aan V / (V + R) + O(1) wanneer m naar oneindig gaat.

Na dit eenvoudige schema kwam de anonieme joodse componist van het lied “Ehad Mi Yode’a” met een schema met geheugencomplexiteit O(√n). Daarna verwijst Knuth naar het lied “Old McDonald had a farm” met een nog lagere complexiteit:

The coefficient of √n was further improved by a Scottish farmer named O. MacDonald, whose construction appears in Lemma 2.

Het liedje “m bottles of beer on the wall” haalt dan weer een complexiteit van O(log n). Volgens Knuth heeft de twintigste eeuw echter iets veel beters opgeleverd:

However, the advent of modern drugs has led to demands for still less memory, and the ultimate improvement of Theorem 1 has consequently just been announced:

THEOREM 2.
There exist arbitrarily long songs of complexity O(1).

PROOF: (due to Casey and the Sunshine Band). Consider the songs Sk defined by (15), but with
Vk = ‘That’s the way,’ U ‘I like it, ‘ U
U = ‘uh huh,’ ‘uh huh’
for all k.