brian hefele's untidy space

(The late) Alan Turing's birthday was yesterday, and I meant to write this post yesterday, but I didn't, so here it is now. Anyone with an interest in computing (note: not computers) already knows everything there is to know about Turing, but for everyone else, here's a little background. Turing was a mathematician (among other things). At the time (let's say late 1920s through 1954), there weren't computer scientists, because there weren't computers, not as we know them. There was a lot of math, though, and one way to help formulate a proof, help work through an algorithm or a complex mathematical function is by having some sort of device to help you.

This device could be mechanical or (by today's standards, primitively) electronic. It could be real, or it could be theoretical. Turing described the concept of what we now call a Turing Machine. This machine has an infinite amount of tape (memory), the tape broken into even segments. The machine reads a segment, and depending on the state of the read, can write onto a segment, and move one step left or right. Such a machine can simulate any algorithm, and so in some sense would replace the need for specialized machines. We call a machine which can simulate any Turing Machine a Universal Turing Machine. This isn't a practical device, especially given the computing power we actually have at our hands these days. But it's a valuable thought experiment, and playground for computational exercises.

Turing did far more than just describe the Turing Machine, of course, but this was what I wanted to focus on right now. Stephen Wolfram wrote a far more complete and far more touching birthday post than I ever could have (and he got his up in time!). What I wanted to ultimately discuss was this: experimenting with a Turing Machine simulator is always a fun way to pass the time, and Turing's birthday (or the day after!) offers a great excuse to try such. A while ago, I was hunting around for a good, CLI Turing machine simulator. There are plenty of GUI programs out there, but they all seem to rely on Java and are quite sluggish for it. I don't really think that something like a Turing Machine simulator has any need to exist in the GUI space anyway, though it does make for a pleasant playground experience.

What I eventually found was one of those little hidden gems of open source¹, the sort that's just a handful of source files, no man page, a barebones makefile (if any at all), the only documentation existing on the site you found it on, the default command name is ridiculously long. They probably don't handle job control right, and might exhibit some other odd behaviors. But someone, some hobbyist, made them for some purpose, probably because they couldn't find anything else at the time to scratch that itch, or perhaps just as an exercise. They're not on Sourceforge, github, Google Code, freshmeat, but regardless they can be charming little bits of software.

So, the one I found is lovingly called Turing Machine Simulator², and it built without any trouble for me. It reads plaintext files for tape and instructions, marked up in an easily read fashion. The interface feels a bit like it was written for DOS users, but that's alright, it works. You load in a file, and then either go through it step-by-step, watching every move of the head along the tape, or you can just have it execute the program and return the results. It's simple, it's clean, and (quirks aside - for instance, this one definitely doesn't like job control) I adore it. So quit reading this, and celebrate (the day after) Turing's birthday instead!

^*1: Not uppercase Open Source, not uppercase Free Software, or any of those other semantically abused terms that exist to give the FSF a wank and a pat on the back. Just software that you get the code to, you can build it yourself, and if it doesn't work, you can fix it if you so desire.

^*2: If you download the source, you don't get the three example files. Download the linux binary as well to get those.