There is something missing here.

If I were to write a "random book generator" that just regurgitate infinite text then I can copyright a pair starting index and length, but not simply all possible finite sequences of letters.

I would argue writing a book, composing a song, or inventing a device should be viewed as a search process. You are wandering around in the space of all possible books, songs, or devices looking for one that is interesting to read, pleasant to listen to, or useful to use. Your work is mainly identifying special items in the vast space of possible items, making it physical once identified is only secondary, at least for the purpose of this discussion. So writing a computer program to generate all possible songs is finding a specific and - at least somewhat - useful program among all possible programs and - ignoring its triviality and the general questions about copyright - seems copyrightable to me. On the other hand using this program to turn the space of all possible songs from something in your head into a huge pile of MIDI files on a disk seems not copyrightable to me because you do not single out interesting songs. Finding a good song did not get significantly easier, searching through and listening to a sea of MIDI files instead of playing all possible combinations of notes on a piano and judging the sound of it.