Computability Discussion with No Evident Investigative Leads

258 Are the Androids Dreaming Yet? this argument, but music is much easier to analyze. It is linear, highly mathematical and largely uniform by culture and language. Yet it is universally appreciated. Is music a computational or a creative endeavor? Is Music Computable To prove a piece of music is non-computable requires two tests. First to show we can ‘reduce’ it to a problem that is already non-computable and, second, to demonstrate it ‘looks like’ or ‘sounds like’ a piece of music. An accountant would say it needs to pass ‘the smell test’. The first non-computable problem to be studied in depth was Emil Post’s Word Problem. Post was a contemporary of Alan Turing and studied at the Institute of Advanced Mathematics in Princeton. He solved the Halting Problem six months before Turing, but his proof used a complex recursive method called the lambda calculus. Turing’s method was far more practical, which is why we now refer to Turing machines rather than Post machines. Later in his career, Post came up with a branch of non-computable mathematics called ‘Post Problems. They look like a puzzle you might find in a newspaper. Imagine starting with the word ‘camel’ and being asked to turn it into ‘aardvark, using only a few simple rules. We'll make the problem very easy to start with: cam © aard and el ovark. This solution is obvious; just do the substitutions and you are there. But what if the rules were a little more complex? Gennadii Makanin, a Russian mathematician based at the University of Moscow, found a set of extremely simple puzzles that are nevertheless non-computable. Here is one: {“CCBB” <> “BBCC”, “BCCCBB” <> “CBBBCC”, “ACCBB” <> “BBA? “ABCCCBB” © “CBBA’, “BBCCBBBBCC” <> “BBCCBBBBCCA’} Word Problem Can a computer tell us which word problems have a solution and which do not? The answer is ‘no. Word substitution puzzles are a class of non-computable problem. Martin Davis proved this in 1948. Using a reduction argument we can use these word problems to prove some music is also non-computable. HOUSE_OVERSIGHT_015948