More Fun with Turing Machines

I have to admit I’m surprised at how nice a reception Turing Drawings received when I linked to my last blog post on Reddit. In only a few days, my blog received over 10K hits, and dozens of redditors shared interesting patterns they had found, some of which were quite amazing.  One thing is clear: without publicly available URLs, this experiment wouldn’t have been nearly as successful. I added many more links to user creations in my previous post for those who might be interested.

Clarifications About Turing Drawings

Some readers asked for better explanations of how Turing Drawings works. The following might clarify some important points:

It’s a Turing machine with a finite 2D grid instead of a linear one-dimensional tape. The machine can only read/write one grid cell (one pixel) at a time. It can also only move left/right/up/down one pixel at each time step (four possible actions). Each cell of the grid directly corresponds to a pixel in the canvas. As the Turing machine runs, it produces something we can interpret as a 2D animation (the symbols written are encoded as pre-selected colors).

The grid is initialized with all cells set to the symbol zero (red color). There are no halting states, as I thought having halting states would cause too many machines to halt very early. Machines technically can’t write the zero symbol, only read it. This constraint is not necessary, but it makes it possible to see where the machine has written (red areas are untouched).

Since the machines are randomly generated, it makes sense that most of them wouldn’t produce interesting patterns. Indeed, if you tried Turing Drawings, you might have had to press the “random” button many times before you saw anything interesting happen. I’m actually quite pleased with how many of them do produce visually interesting things though. This is the reason I chose to use Turing machines for this project: to maximize the likelihood of visually interesting things happening.

Turing machines are a very simple model of computation. This model was easy to tailor for my purposes: with a 2D tape mapping to a pixel array instead of a linear tape. It was also easy to make sure the Turing machines wouldn’t terminate by construction by giving them no halting states. Unfortunately, I can’t design an algorithm that generates interesting visuals “by construction”, because I really have no way of mathematically quantifying what will please your eyes, but by restricting ourselves to smaller programs with few transition rules, we make it fairly likely that some order will emerge out of the chaos that created the machines. This is really what Turing Drawings is all about: order and complexity emerging out of a few simple (transition) rules chosen at random.

Turing Tunes

I’ve been interested in procedural generation of music for some time, and as soon as I saw how well Turing Drawings worked out, I immediately started planning another project: Turing Tunes. I believe that generating music procedurally is probably trickier than generating visuals, because while visuals may seem plain or uninteresting, many sounds are actually irritating to the human ear. Fortunately, there are some tricks we can employ to reduce the probability of cacophony. By default, Turing Tunes will generate musical notes in a pentatonic scale. This type of scale is known for its lack of dissonant intervals and is particularly suitable for improvised music.

My current plan is to use a Turing machine with two tapes. A one-dimensional bidirectional working tape (hidden internal memory, scratch space), and a unidirectional output tape where musical notes are written. The memory tape will have a fixed size and loop over on overflow. The output tape will receive musical notes/duration pairs and will not be erasable. The machine will only be able to write new notes, but never remove them. This ensures, by construction, that machines can only produce more musical notes over time.

I should mention that I already have a prototype of Turing Tunes working and generating musical notes, but I’m trying to polish this a little more before I make it available on github. I’m not sure what’s the best sounding musical instrument to use for this. For now, I’m using the plucked lead instrument from my MusicToy app. I want to add a streaming piano roll animation that shows the notes generated.

I also plan on implementing some kind of automated filter to quickly reject tunes that don’t work out. I mentioned earlier that you might need to generate many machines in Turing Drawings before anything interesting happens. The same is true in Turing Tunes, but listening to tunes takes longer than looking at 2D pictures, and so filtering through dull one or two note loops by hand is rather tiring.

I have a few strategies I plan to use for filtering:

• Filtering out machines that only produce a few notes and then get stuck in a loop
• Filtering out machines that produce short repeating loops
• Computing the Shannon entropy of the output

None of these strategies are perfect, they will all be approximations, but I believe it should be possible to filter out most “duds” and make it so the user is exposed to less junk and more interesting output.