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
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.)
n
1'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 n
+m
+1
ones (and not n
+m
+2 ones).
(Shelburne: add.tms)n
+m
+1, not
n
+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
function
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-compose
function. 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
used gturing2tms.el
routines to translate them.
Here's my version: clean.tur. It's
a bit more efficient, but can still be improved (why do I
waste time going to the right at the start?).
(Shelburne: CLEAN2, clean.tms)