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.
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
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.
composes two gturing programs. Given machines
s, it calculates the machine which first does
t and then does
s (using the output
t). Very handy! I include some of the results
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.)
n1's to the decimal representation for
n). I cheated by using a * here (which is not part of the input/output alphabet), but that * is eliminable. (Shelburne: u2d.tms)
n+1 ones and another block of
m+1 ones, it returns a tape with
m+1 ones (and not
m+2 ones). (Shelburne: add.tms)
m-- the conversion does not account for the fact that a single 1 denotes 0 in the Boolos, et al., convention.) (Shelburne: u2d-after-add.tms)
This machine does not represent multiplication in the
technical sense of Boolos, et al. It represents the
f(x,y) = (x+1) * (y + 1) - 1.
See the text for the definition of when a machine computes a function to understand why this is so. (Shelburne: MultJeffreyBoolos.tms)
gturing-composefunction. I had hoped this would have the effect of tripling a block of ones. It does, but there's an extra space between the first two blocks. I won't bother to fix it, but instead include it here as an example of what composition can do. Now if someone else writes a function to move that first block over by one, the resulting composition would give me what I wanted. Good (easy) homework exercise. (Shelburne: double-after-skip-after-double.tms)
The following programs were written by Melissa van Amerongen.
She wrote them for the Shelburne Turing Machine Simulator, and I
gturing2tms.el routines to translate them.