Jason Hemann and I recently had a paper accepted at FARM called “Visualizing the Turing Tarpit.” The idea grew out of a talk that Jason did at our weekly PL Wonks seminar on the minimalist programming languages, Iota and Jot. At the end of the talk, Ken Shan asked whether this could be used to do some kind of cool fractal visualization of programs. That night, several of us pulled out our computers and started hacking on Iota and Jot interpreters.

Iota and Jot are examples of Turing Tarpits, that is, languages “in which everything is possible but nothing of interest is easy.” The term comes from Alan Perlis. Turing Tarpits have some utility. The Lambda Calculus is arguably a Turing Tarpit, and yet it is quite useful in the study of programming languages and computability. Iota is notable as a Turing-complete language which consists of only two symbols. For example, i, *i*ii, and **iii are all legal programs in Iota. Sadly, some strings, such as i*i are not legal. This makes Iota less than ideal for enumerating many programs, as we can’t choose arbitrary strings but must instead be sure we follow the grammar. Jot was designed to fix this. Jot has the property that any binary string is a legal program.

Using Jot, it’s now incredibly easy to enumerate large numbers of programs. The next step is to plot the behavior. We chose to see how many steps a program executes for before terminating (or until we give up, as not all programs will terminate), and then use this to generate a color for a certain point. Below is an animated example of what we ended up with.

This visualization works by generating a random bit string, then converting it to a real number, and then mapping this into 2D space using a Hilbert Curve. The color indicates how long the program at that point took to execute, and the larger dots also indicate longer-running programs. Black dots indicate programs that didn’t terminate in time.

You can see this and several other examples on our gallery page. You can see more details about our approach in our paper.