Visualizing the Turing Tarpit
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.