Sample gturing programs

I have made available a few sample Turing machine programs suitable for use with gturing, the Gnome Turing machine emulator.

If you've come here looking for solutions to homework problems, shame on you. I hope that none of these programs match your assignment. Certainly, you do not have permission to take any of my work and submit it as your own. On the other hand, if you've come here for examples to help you write your own programs, then please have a look around. If you have any programs you'd like to share, please let me know and I'll include them here.

Many of these programs were written to be used with the Boolos, Burgess and Jeffrey book, Logic and Computation (4th edition). There is a difference between their formalism and gturing's, though. Boolos, et al., have four actions: read, write, move left and move right. gturing has two actions (read and write) and additionally requires a move instruction for every "line". Of course, it's little work to translate one formalism to the other.

Turing

I found a Turing emulator for Windows at this site, written by Brian Shelburne. The format is similar to gturing, but a little different.

I wrote an emacs-lisp translator to translate gturing programs to the format of Shelburne's simulator and vice versa. I include the translations here. I also include the emacs-lisp in gturing2tms.el. This file has two translation functions, gturing2tms and tms2gturing. If I ever get around to it, I will add translations for the format that Boolos, Burgess and Jeffrey uses. This will be a touch trickier, but not much.

There is also a third function in gturing2tms.el. gturing-compose composes two gturing programs. Given machines t and s, it calculates the machine which first does t and then does s (using the output from t). Very handy! I include some of the results below.

You need to use Emacs or Xemacs to use my translation and composition routines. Of course, all right-thinking people are already using Emacs or Xemacs or both.

If you have any sample gturing routines that you'd like to make available, I'd be happy to put them here. Just write me. Also, let me know if any of these programs fail to work as advertised. (Probably I'll change the advertisement.)

The following programs were written by Melissa van Amerongen. She wrote them for the Shelburne Turing Machine Simulator, and I used gturing2tms.el routines to translate them.

<-- http://www.bcri.ucc.ie/~dw5/download/NearyWoods-TCS-06.pdf -->
Jesse F. Hughes
Last modified: Fri Mar 7 08:43:33 EST 2008