The Complexity of Songs

The Complexity of Songs ( en , de : About the complexity of songs ) is a scientific joke publishedin 1977 by the computer scientist Donald Ervin Knuth . In it he analyzes the length of songs depending on the text to be learned using the methods of complexity theory . The article also polemicizes an alleged tendency in popular music from complex ballads to strongly repetitive texts or triviality . It was first published in 1977 in SIGACT News , and in 1984 the article wasreprintedin the Communications of the ACM .

Summary

Knuth's article opens with the observation that singing most songs of length requires learning the lyrics of length . As the number of songs increases, this property strains the storage capacity of the memory . As a simple concept for managing memory more efficiently, he introduces the concept of the refrain . In a first lemma he uses an elementary calculation to prove that this concept can reduce the required storage capacity by a constant factor . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle c <1}$

Immediately afterwards he analyzes a concept that further improves this result: Using the song Echad Mi Yodea ( he : אחד מי יודע, ji : ver ken zogn ver ken redn ) he proves the existence of songs with asymptotic storage complexity of . He cites the song Green Grow the Rushes, O , (also The Dilly Song ) Alouette , Isn't that a Schnitzelbank and other songs with this structure as conceptually comparable . As an improvement in the coefficient , he discusses the structure of the song Old McDonald had a Farm at length in a lemma. ${\ displaystyle {\ mathcal {O}} ({\ sqrt {n}})}$

In a study of Zählreimen the example based on 99 Bottles of Beer constructed he songs with logarithmic memory requirements, so . For this he looks at the scheme with the verses . he sets ${\ displaystyle {\ mathcal {O}} (\ log n)}$ ${\ displaystyle V_ {k}}$

${\ displaystyle {\ begin {aligned} V_ {k} = & T_ {k} \ ast B \ ast W \ ast ',' \\ & T_ {k} \ ast B \ ast ';' \\ & '{\ mbox {If one of those bottles should happen to fall,}} '\\ & T_ {k-1} \ ast B \ ast W \ ast'. '\ End {aligned}}}$

It is

${\ displaystyle {\ begin {aligned} B & = '{\ mbox {bottles of Beer}}' \\ W & = '{\ mbox {on the Wall}}' \ end {aligned}}}$

${\ displaystyle \ ast}$ is the concatenation of strings and an embedding of the natural number in the English language. Due to the logarithmic number representation of the decimal system , an embedding can be constructed with logarithmic memory expenditure. Obviously, the recursively declared songs with , the empty song , and have a logarithmic complexity for large . ${\ displaystyle T_ {k}}$ ${\ displaystyle k}$ ${\ displaystyle L_ {n}}$ ${\ displaystyle L_ {0} = \ varepsilon}$ ${\ displaystyle L_ {n + 1} = V_ {n + 1} \ ast L_ {n}}$ ${\ displaystyle n \ in \ mathbb {N}}$

This result has proven to be more than sufficient in all situations that require a generation of songs with limited storage space. He sees a structure that cannot be further optimized in the song That's the Way (I Like It) by the American band KC and the Sunshine Band . He sees the development of this structure as the necessity of larger song instances with minimal storage space due to the progress of modern drug technology. In a short argument he proves its constant complexity ( ) and closes his paper with a reference to the open problem of studying non- deterministic song structures. (see aleatoric ) ${\ displaystyle {\ mathcal {O}} (1)}$

Receptions

In a letter to the editor to the ACM, Kurt Eisemann ( San Diego State University ) pointed out a well-known improvement in the complexity estimation by considering it as above. If you implement , you have an improvement on the method proposed by Knuth . A complexity of can be achieved through the use of silent data structures . Darrah Chavey took Knuth's idea seriously to develop a didactic approach to explain computer science methods. ${\ displaystyle L_ {n}}$ ${\ displaystyle V_ {k} = '{\ mbox {la}}'}$ ${\ displaystyle c = {\ frac {2} {53}} = 0.037736 \ dots}$ ${\ displaystyle {\ mathcal {O}} (0)}$

Remarks

↑ For the notation see Landau symbol .

↑ Original wording : However, the advent of modern drugs has led to demands for still less memory space.

Individual evidence

^ Steven Krantz: Mathematical Apocrypha Redux . 2005, ISBN 0-88385-554-2 , pp. 2, 3.

^ Donald E. Knuth : The complexity of songs . ( Memento of the original from December 26, 2005 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF) In: SIGACT News , Summer 1977, pp. 17–24. Reprint in Commun. ACM , 27, no. 4 (1984), pp. 344-346, doi: 10.1145 / 358027.358042 @1@ 2
↑ Green Grow the Rushes, O ( Wikisource )
^ K. Eisemann, Letter: Further Results on The Complexity of Songs , Comm. ACM, 1985, 28 (3), 235.
↑ Darrah Chavey: Songs and the analysis of algorithms . In: Proceedings of the twenty-seventh SIGCSE technical symposium on Computer science education (Philadelphia PA, United States: ACM, 1996), pp. 4-8, doi: 10.1145 / 236452.236475

[3] For the notation see Landau symbol .

[1] Steven Krantz: Mathematical Apocrypha Redux . 2005, ISBN 0-88385-554-2 , pp. 2, 3.