After watching a documentary about Alan Turing, I started thinking about Turing machines again. They’re a very useful tool for computer science proofs and an elegantly simple computational model. Beyond this, however, Turing machines seem relatively useless in terms of “real-world” applications. Any computable function can be computed by a Turing machine, but you probably wouldn’t want to use one as a compilation target: it would be too inefficient.
One possible application for Turing machines is to use them as programs to generate data procedurally. Their simplicity makes it possible, for example, to create working programs randomly. Generating a random stream of x86 instructions that doesn’t crash could be tricky, but with a Turing machine, it’s quite easy. I decided to try something like this to produce so-called generative art. The program I wrote generates random Turing machines that operate on a two-dimensional grid instead of a one-dimensional tape. The symbols written on the grid can be interpreted as colors, and voilà: we have procedural drawings.
Last night, by chance, I randomly generated something that looked very much like the Sierpinski fractal, but unfortunately lost the encoding for that one. If you happen to find fractal patterns, be sure to let me know!
EDIT: seems the people on reddit.com/r/compsci have gotten pretty excited about this. I’m surprised at how much of a positive response I got. Here are some of the nicest patterns they’ve found:
- Sierpinski-esque fractal (thanks trq)
- More Sierpinski (thanks moyix)
- Sierpinski over two (thanks Peter)
- Sierpinski in black (thanks sssh)
- Quad Fractal (thanks Spencer)
- Awesome thing 1
- Spikey Flowing Thing
- Modern art
- Green waves
- It’s the Matrix
- Moss vs. escalators
- Rain streaks
- Spears, roots, fins
- Blow away
- Cubes to Chaos
- Different style of waves
- Gradual 1
- Gradual 2
- Rain on a window
- Floor cracks, fungus rise
- Traveling Grass
- Breaking point
- Ice lines
- Leaky fractal
For future work, I’m thinking it might be interesting to try using Turing machines to generate music procedurally. Certainly, music could be represented by notes on a tape, or even multiple tapes.