The Complexity of Songs
The Complexity of Songs (en, de: On the complexity of songs ) is a 1977 report published by the computer scientist Donald Knuth Ervin articles and scientific joke. He analyzes the length of songs, depending on the text to be learned by the methods of complexity theory. The article also polemicizes an alleged tendency of popular music of complex ballads to highly repetitive texts or triviality. The first publication was in 1977 in SIGACT News, 1984, the article in the Communications of the ACM was reprinted.
Summary
Knuth's article opens with the observation that singing the most songs of the length requires the learning of text length. Given the growing number song this property strapaziere the storage of memory. As a simple approach for the efficient management of memory, he introduces the concept of the refrain. In a first lemma proves it with an elementary account that this approach can reduce the required memory by a constant factor.
Directly after he analyzed a concept that further improved this result: Based on the song Echad Mi Yodea (hey: אחד מי יודע, ji: ver ver ken ken ZOGN redn ) he proves the existence of songs with asymptotic space complexity of [. a 1 ] As conceptually comparable he calls the song Green Grow the Rushes, O, (also the Dilly song) Alouette, Is not that a Schnitzel Bank and other songs with this structure. As an improvement in the coefficient he discusses the structure of the song Old McDonald had a farm detail in a lemma.
In a study of Zählreimen using the example of 99 Bottles of Beer constructing songs with logarithmic memory requirements, ie. He looks for the schema with the verses. here he is
It is
Is the concatenation of strings and an embedding of the natural number in the English language. Due to the logarithmic representation of the decimal number is an embedding with logarithmic memory overhead can be so constructed. Obviously then have the recursively declared songs with the empty song, and a logarithmic complexity for large.
This result has been proven in all situations that require a song generation with limited space, as more than adequate. A not optimizable structure he sees in the song That's the Way ( I Like It) of the U.S. band KC and the Sunshine Band. The development of this structure he sees the need for greater song instances with minimal memory space by the progress of modern drug technology related. [A 2] He proves in a short argument whose constant complexity ( ) and his paper concludes by pointing to the open problem of the study of non-deterministic song structures. (see aleatoric )
Receptions
In a letter to the ACM had Kurt Eisemann (San Diego State University) indicate a known improvement of the complexity estimation by the must be regarded as above. Substituting, we have an improvement of the proposed method by Knuth. A complexity can be achieved by the use of hidden data structures. Darrah Chavey grabbed Knuth's idea seriously to develop a didactic approach to the explanation of methods of computer science.