Hacker News new | past | comments | ask | show | jobs | submit login
The Complexity of Songs (1977) [pdf] (psu.ac.th)
28 points by Hooke 6 months ago | hide | past | web | favorite | 9 comments

Music Was Better in the Sixties, Man


The title of the paper is misleading and it made me dissapointed. This should not be a tounge-in-the-cheek joke but should be about the complexity of a song - but it only counts some verses and refrens. Doesn't even have to be a song...

Anyhow I think a song gets more complex as it more commonly breaks the patterns the human mind finds in them.

Why do you say that something written and intended as a joke “should not” be a tongue-in-cheek joke?

Because the topic was really interesting to me and I wanted to read about it! :( It rarely happens that I read the title of a paper and immediately want more than a peek. I got excited then got disappointed by a flat joke. Not funny.

This paper always makes me sad because there are real things to be said about the structure of repetition in music, but Knuth treats it as a joke.

Does making a joke about something imply that there aren't “real” things to be said about it?

To put it differently: here, Knuth heard a popular song that seems to be just “That's the way uh huh uh huh I like it uh huh uh huh” repeated endlessly, found it funny, and wrote an elaborate joke culminating in that observation, hewing to the style of CS publications. Why does that make you sad? It's not as if someone's bit of humour has prevented others from saying “real things”.

It's not even a good joke. The song has two verses as well as the repetitive chorus, and he ignores them for the sake of the joke.

I find the whole paper very funny (see my other comment: https://news.ycombinator.com/item?id=18048229) but of course tastes can differ. Not sure though why you'd find it sad if someone made a joke you don't find very funny.

In typical Knuth style, there are so many jokes here beyond the central idea of the paper itself! With apologies for explaining jokes...

It is known [3] that almost all songs of length n require a text of length ~ n — here the reference [3] is not a reference to the musical literature as one might expect, but a reference to Chaitin! This is similar to Kolmogorov complexity, “almost all real numbers are uncomputable / undefinable”, etc. :-)

By the Distributive Law and the Commutative Law [4], we have — a reference to Chrystal, the standard algebra textbook of the 19th century. (See also Underwood Dudley's “What is Mathematics For?”)

possible to generalize this lemma [...] provided that the sequence <V_k> satisfies a certain smoothness condition. Details will appear in a future paper — typical papers (and of course even the author knows there will no future paper) :-) Cf. Polya's “cheap” generalization.

The coefficient of √n was further improved by a Scottish farmer named O. MacDonald — even when making a joke, he has a serious reference to Kennedy's book on folk songs, giving the page number where other farmyard songs are discussed. In fact the entire list of references is rather scholarly.

R₁ = ‘Ee-igh, ’² ‘oh! ’ — the ² here is not a footnote, but “square”, i.e. the string repeated two times

• The whole proof of Lemma 2 is a wonderful (and educational) formalization of the song

Therefore if MacDonald's farm animals ultimately have long names they should make slightly shorter noises.

A fundamental improvement was claimed in England in 1824, when the true love of U. Jack gave to him a total of 12 ladies dancing, 22 lords a-leaping, 30 drummers drumming, [...] during the twelve days of Christmas [11] — the reference [11] is a reference to a MoMA artwork, see https://www.worthpoint.com/worthopedia/ben-shahn-titled-book...

(see [7]) — the [7] here is a faux reference; it reads ”U. Jack, "Logarithmic growth of verses," Acta Perdix 15 (1826), 1-65535” and apart from “U. Jack” and the number of pages, note that “Perdix” = partridge

J. W. Blatz of Milwaukee, Wisconsin who first discovered a class of songs known as "m Bottles of Beer on the Wall"; her elegant construction... — Knuth is from Milwaukee, Wisconsin, and J. W. Blatz is https://en.wikipedia.org/wiki/Valentin_Blatz_Brewing_Company

the song "I'll drink m if you'll drink m + 1." However, the English start at m = 1 and get no higher than m = 9, possibly because they actually drink the beer instead of allowing the bottles to fall.

all practical requirements for song generation with limited memory space. In fact, 99 bottles of beer usually seemed to be more than sufficient in most cases.

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

• [Well you should just read it]

Acknowledgment. I wish to thank J. M. Knuth and J. S. Knuth for suggesting the topic of this paper. — finally giving away the reason for the existence of this article: these are his children; they were probably 12 and 10 at the time.

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact