[New Kind of Music and NP-complete problems] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


New Kind of Music and NP-complete problems

(Click here to view the original thread with full colors/images)


Posted by: Craig Feinstein

I checked out a New Kind of Music here:

http://tones.wolfram.com/

It's certainly an interesting idea. Apparently, there are some other computer programs out there which also make computer-generated music:

http://en.wikipedia.org/wiki/Algorithmic_composition

One thing that struck me when listening to some of the tunes generated by the Wolfram program is that none of them were particularly great music, certainly not Mozart quality, nor even American Top 40 quality.

However, none of the tunes generated by the program were particularly horrible-sounding either. It appears that the New Kind of Music algorithm was designed in which all of its tunes satisify some basic rules of composition so that the music generated does not sound horrible. Also, it appears to be relatively easy to program a computer to do such. However, I would not be surprised if programming a computer to write *great* music is much more difficult.

Perhaps, we could think of this in terms of computational-complexity theory, as the following conjecture: There are programs out there which run in polynomial-time and consistently find music that does not sound horrible. But there are no programs out there which run in polynomial-time and consistently find *great* music, because finding *great* music is a problem in NP but not P. This has been suggested before:

http://weblog.fortnow.com/2005/03/pnp-and-arts.html

If we could show that finding *great* music is in NP but not P, then the fact that there are composers like Mozart give evidence that our brains cannot be modeled as deterministic computers.

I welcome any comments.


Posted by: Vasily Shirin

Problem of writing music is not an algorithmic problem, so neither P nor NP are applicable terms here. There's a human dimension in it, so it's very dissimilar to, say, chess game, which is relatively easy to formalize. In composition, formalization of your GOAL is impossible within computer science. Music should make sense for human, and "sense" is a very vague notion
(as you can easily guess, formalization of notion
of sense, or meaning, is absolutely impossible: you will get stuck while trying to define the meaning of the notion of "meaning" itself).
BTW, have you ever noticed that straightforward playback of written notes sounds ugly, even if it's a really great piece of music? It takes a great performer to play great music. You can't outsource even this seemingly trivial job to your computer.


Posted by: Craig Feinstein

I agree with you to some extent, that it is difficult to formalize what great music is, that doing such is very fuzzy. However, I wouldn't give up on this either. There are certain characteristics of compositions which make music great. These characteristics are apparently easy to recognize, i.e., it is easy for most people to recognize that Mozart wrote great music; however, to compose music as great as Mozart's music is very difficult.

An analogy is as follows: It is easy to verify that the following 16x16 matrix A of +1's and -1's (I'll abbreviate + for +1 and - for -1) is a Hadamard matrix, i.e., A*A^t=16*I.

++++++++++++++++
+-+-+-+-+-+-+-+-
++--++--++--++--
+--++--++--++--+
++++----++++----
+-+--+-++-+--+-+
++----++++----++
+--+-++-+--+-++-
++++++++--------
++++--------++++
++--+-+---++-+-+
++---+-+--+++-+-
+-+-+--+-+-+-++-
+-+--++--+-++--+
+--+++---++---++
+--+--++-++-++--

However, finding such a matrix is much more difficult than verifying that it is Hadamard. (You can't program a computer to find such a 16x16 matrix by exhaustive search in real-time.)
*Human* mathematicians found this matrix by using a different method, just as Mozart didn't exhaustively search the entire set of possible music compositions to write his music.

I'm not an expert on music, but I am guessing that great music has properties similar to the Hadamard matrix in that it satisfies some characteristics which are easily recognizable and easy to state, yet difficult to actualize.

Based on my experiments with New Kind of Music, it appears that their way of generating music is not guaranteed to write *great* music; if it ends up writing *great* music, then it's by luck that it does.

However, the methodology does do a great job at producing music which has the complex characteristics of *great* music, without sounding horrible, which was probably the intention of the authors of New Kind of Music.


Posted by: Todd Rowland

If the problem with music could be roughly stated to create a great piece of music of size n, then it could be put into a time complexity class like NP complete. What about the problem of recognizing if a piece was great music? That seems to be at least as difficult, from a computational point of view. (To be in NP, you need to be able to check a solution in polynomial time.)

From an NKS point of view, one takes advantage of the power of simple rules, in this case the power to create music. So instead of trying to compute meaningful music, the idea is to search candidate compositions until you find something good. I think tones is meant to give candidates and you just have to do the searching.

It would be interesting if the idea of computing music could be formalized further from an NKS perspective.


Posted by: Dorax7

Music can be an NP problem. I have written a computer program where the computer generates a sequence of random notes and lengths of those notes as a start (based on a given scale).

Then I designed a function to give a score to that fagment, based on things like: how many notes actually come from the scale, how consistent is the rythm etc...
This is of course the most important and hardest thing to design. It's hard to actually find these criteria.

Based on the score the music can be evaluated. A TABU SEARCH metaheuristic I developed then tries to search for the best music fragment. No personal choise needed.

Voilą, that's definately an optimization problem.
The program is called tabumusic, I have it on sourceforge.net

Wat would be interesting is to judge music on a frequency basis, so using fourrier. But I haven't gotten around to that...


Posted by: Val Smith

I've been researching so long that I predicted well in advance on this forum that Wolfram Tones would be announced:

http://forum.wolframscience.com/sho...hp?threadid=780

Lets assume the finite range of human hearing,
and make it a little worse,
say like telephone music on hold
or AM radio,

And also assume that 4 minutes is the average
length of music that people prefer to listen to,

And that 4 megabytes is sufficient to store
all possibilities with these constraints.

And that if a million people with a million
tape recorders recorded a performance
with that quality, then digitized it...

There would be a million unique recordings
that sound very similar and fit in the
memory, yet a million more are possible.

And that not everything that fits in the
memory can be playback as physically
possible sound.

And that there is no sound that doesn't
enumerate higher than the highest
number that is storable in the memory.

Well, these assumptions are true,
and my experiments with the SET of
data constrained by them is
remarkably free of Static, and
remarkably rhythmic and melodious,
though I have not heard yet more than
ONE familiar song in it, and many of it's
redundancies, which I searched for
intentionally.

(Of course we don't live long enough
to hear every song already sung!
And the SET includes those yet unsung.)

The familiar song found in this set is
Pocket Calculator,
and many integers are interpreted by
human ears to sound like it, which
can fit in a small memory chip.

The player of this musical Set can be made
so simple that I published it as a
science project, but unless Mathematica
has a plugin for playing graphs as sounds
in real time, it remains true that a hundred
programmers have seen heard and
understood my code, written on a napkin,
which plays neverending "music",
but none have succeeded in running
it on a PC, except some unknown
demoscene coder, perhaps.

I doubt AM quality would render
unrecognizable any tune,
thus there is for certain by far much less
unique music than a number
written as 4 million 9's
or 4 million 1's in binary.

All that I have said and done,
if heard in court, should have
marginalized Napster, and if only
this generation could do basic
arithmetic they could not be sued.

OMNIBUS EX NIHILO, DUCENDIS SUFFICIT UNUM.
(To create everything from nothing, ONE is sufficient.)
-Leibniz, contemplating Binary numbers.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings