On Computable Numbers and Satisfiable Sounds

Trevor Smith and I are teaming up: this is our first offering in a series of monthly posts pairing interesting computer science articles with classical music.

Listen to this:  Gondwana by Tristan Murail

Read this:  On Computable Numbers by Alan Turing

Alan Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem is a seminal paper. Anyone taking a CS undergraduate core will encounter the notion of computability and the halting problem. Further from the ivory tower, it is not difficult to find people who are near-giddy about Turing Completeness:

Breaking news: HTML + CSS3 is Turing Complete,

People looking for help developing a Turing machine in Microsoft Excel,

A Turing machine built using Legos,

and Brainfuck, a language whose website describes it as “an eight instruction Turing-Complete Programming Language”.

Turing’s name has become quite literally a “formal” stamp of approval in the computing world.

Beyond a few feeble mechanical attempts, computers did not exist in 1936, and Mr. Turing didn’t appear that excited about making one — he was interested in making Godel’s work on incompleteness comprehensible. That is, Turing wanted to intuitively construct a class of decision problems that could be proven undecidable. Turing could not tackle this without defining a notion of “computable”. His definition leaned heavily on a few notions that we would recognize today as common, but required a little more formal attention-to-detail back then:

Turing describes memory:

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, …. qI; which will be called ” m-configurations”

and the idea of output:

… the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

Academic language aside, the machine Turing is defining is simple. Simple like a paper and pen are simple; simple like the gestalt of piles and piles of modern integrated circuits that is DRAM is not. Turing calls this machine an “‘automatic-machine’ (or alpha-machine)”. The machine has the following properties:

a tape divided into squares

symbols that are on the squares

the scanned symbol (the rth symbol). Modern texts will likely refer to this as the symbol the ‘head’ is pointing to.

configuration: the current m-configuration and the current scanned symbol (qn, G(r))

But this paper is not without its difficulties, especially when approaching it today (ie: we found this paper to be very long, tedious and arduous).

One initial difficulty: having both completed somewhat standard undergraduate classes in formal computation theory, the initial choice of terminology by Turing of “Circle-free” and “Circular” was extremely confusing to our modern eyes. Most undergraduates approach Turing’s ideas in their coursework from the “halting problem” angle. What is initially confusing here is the following:

CIRCLE-FREE != HALTS

How can this be? Turing quickly skirts over the definition of a circle-free machine early on in the paper when he describes it as the following:

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free. A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind.

(p. 233)

Finite. This should be the same as a machine that “halts”, right?

No. Turing’s machines are built to write down numbers. These numbers are (somewhat sneakily) implied to be repeating binary decimals on page 232:

The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine

So we’re essentially talking about endlessly repeating floats–the kind of numbers that you get when you type in [1] [/] [3] on a calculator, except in binary. Numbers with bars over the top of the last digit: 0.33333333…. for example (0.010101010… in binary). In Turing’s paper, the machine that prints 0.010101010… is “circle-free”, meaning it encounters no “terminal difficulty” in computation if it can keep printing out the endless decimal representation without pausing indefinitely to calculate. By this definition, “finite” numbers such as 4, 5, and 6 would be circle-free numbers, because the machine would just print out a sequence of zeroes after the decimal point: 6.000000000…. “Halting” really has no place in his discussion — for if we took a machine that “did not halt” by the “halting problem definition”, it would print out, say, 6.000 and then wait for an indefinite amount of time before printing out the next zero.

Understanding the important concept of a circle-free machine is critical, even if your only goal in reading the Turing is to see Godel’s diagonalization “done simply” (see the argument on page 247 of the article, where he argues that the machine H is circular by suggesting an infinite loop).

Why the Murail?

We thought long and hard about this. The Murail represents a significant representative work of a genre, spectral music, that has significant parallels with the work of Turing. Spectral music is detailed well in this wikipedia article

The Murail, like the Turing, uses an intuitive language, completely divorced from the method-as-music ideal of serialism (about serial music). Gondwana is based entirely off of the first sounds you hear in the piece — it is the subsequent deconstruction that leads the listener down a path that is nearly always defined momentarily — “the next sound will be a little more interesting than the one you’re hearing right now, but will not break the continuity of what has already been heard.”

The work starts off very simply. The piece begins with 7-8 moments of repeated sound (see 0:12, 0:30, 0:46, 1:01, 1:15, 1:28, 1:38, 1:48, and then MAYBE [1:55, 2:01, 2:07, 2:13-2:40] in the link here), as easily understood derivations from a simple sonic idea. We had better remember this sound because, after about two and a half minutes, it becomes very clear that this work of music has ambitions beyond repetition.

Indeed, these events are like Turing’s “appeal to intuition” by Murail. There is no recognition of pattern possible without repetition. With the seven chime-strike chords, Murail is handing us a ball of yarn — we will need it to find our way home from the complicated, thorny walk in the woods that is the rest of the piece. There is not going to be a resounding return; no recapitulation here. Every time I hear the piece, I think of the opening of the Turing — the simple tone initially adopted by Turing could easily have been transcribed from a 1930s fireside-style radio broadcast, especially when contrasted with some of the machinations used later in the paper (which are not without their errata — see turing errata for more info).

Beyond the opening, the Murail begins to dig deep into the essence of sound. At roughly 8 minutes into the work, a hissing begins to become a main sonic feature. The connection to the beginning is simple — there is a brief, percussive sound at the beginning of the piece with a few strings playing, perhaps a maracca — there are lots of high partials in that sound. But it brings to mind an important question — a question that is at the heart of spectral music: what kind of music is happening in the parts of sound waves that we DON’T hear? What about all the extremely high partials that dogs can hear? Above, those, even? They exist. They have to. A sound wave can be encoded by a number. Large numbers exist. What if we slowed the noise, say, of water molecules at room temperature bouncing around inside a mason jar? Anyone that has been distracted by the sound of a tea kettle on the verge of boiling already knows that interesting sonic things can happen with water molecules on the surface of a boiling hotplate. But what about beyond the ear? What types of patterns exist at this sonic level of our world?

This is an interesting question that could use additional explanation. A strong argument can be made that much of “Western Harmony” can be boiled down into small, rational-number relationships between different frequencies. Numbers, in fact, that are easily computable by a Turing machine (with a reasonable “skeleton table,” even!). A major triad, for example, is little more than 1X, (5/4)X, (3/2)X (I, III, V). By the standards of Murail (and Turing, for that matter), these are small numbers, and the human ear is quite adept at doing the math of recognizing them and placing them in the context of “sounding good.” The human ear, from a perspective of what it can “understand” in this way, is quite good. We like minor chords, diminished chords, heck, we’ll even listen to Coltrane. Serial music is tougher. In general, music that doesn’t “sound good” to the western ear because of dissonance, etc. likely involves sound frequency relationships that make use of larger numbers. A minor chord, for example, requires use of the 6th and 8th partials. What is the limit? What is uncomputable for the human ear?

Note:
Parallels with music aside, readers not familiar with Turing’s life and the circumstances of his death should read this: turing wikipedia article. Oppression and intolerance are real, and Turing suffered greatly at the hands of the British government.

This entry was posted in Uncategorized. Bookmark the permalink.

Comments are closed.