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.

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.)

• u2d.tur: a converter for unary-to-decimal (changes 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)
• double_ones.tur: an implementation of the Boolos, Burgess and Jeffrey program which doubles the number of 1's on the tape. (Shelburne: double_ones.tms)
• mult.tur: a multiplication program. Input should be 11..11011..11, and output is the product. Note that's a 0 in between the two numbers, not a blank. Why? I don't recall why I wrote it that way. Stupid, I guess. Also, this routine "cheats" as far as Boolos, et al., are concerned. Besides blank, 1 and 0, it uses other characters. I wrote it for play long before I saw that book. (Shelburne: mult.tms)
• add.tur An implementation of addition, according to the Boolos, et al., convention for Turing computability. This means, given a tape with a block of 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)
• u2d-after-add.tur A composition of add.tur with u2d.tur. This means that, after the addition, the result is converted to decimal representation. (But the decimal representation is 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)
• MultJeffreyBoolos.tur: An implementation of the Boolos, Burgess and Jeffrey algorithm. This multiplies two numbers and gives their unary product. The numbers are represented as sequences of 1's with a single space in between, and the product is again a sequence of 1's. The algorithm, then, requires that the two numbers are strictly positive.

  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)

• MultJeffreyBoolosDecimal.tur: As above, but the resulting product is translated to decimal. The input must still be unary, however, since I haven't written a decimal-to-unary converter. I wrote this just because I got tired of counting 1's to see if my program worked. (I did not do this using my composition routine from gturing2tms.el, since it had not yet been written.) (Shelburne: MultJeffreyBoolosDecimal.tms)
• Palindrome.tur: A machine which halts with blank tape if the input was a palindrome. This sample program is included with Shelburne's simulator. It has been translated to gturing format by my translation functions. It is included here by permission of Brian Shelburne. (Shelburne: Palindrome.tms)
• double.tur: Takes a single block of ones and clones it (so the output tape has two blocks). (Shelburne: double.tms)
• skip.tur: Given a tape with two or more blocks of ones, it skips the first and goes to the leftmost one in the second block. (Shelburne: skip.tms)
• skip-after-double.tur: A program created by the composition function in gturing2tms.el. Runs double.tur and then skip.tur. (Shelburne: skip-after-double.tms)
• double-after-skip-after-double.tur A composition of double, then skip, then double, using my 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.

• 1_ADDITION.tur This machine represents addition according to the Boolos notion of Turing computable. This means that a tape with a block of n + 1 ones and another block of m + 1 ones yields a tape of n + m + 1 ones (and not n + m + 2!). (Shelburne: 1_ADDITION)
• 2_INVERSE.tur A simple function that takes a tape with zeroes, ones and blanks and converts zeroes to ones and vice versa. (Shelburne: 2_INVERSE)
• CLEAN2.tur Takes two blocks of ones separated by an arbitrary number of spaces and returns a tape with the "same" two blocks separated by a single space. Perhaps not the most efficient way of doing it, but pretty cute.

  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)

• A universal Turing machine, sent in by Corey Sweeney. He says this is the four symbol, seven state UTM by Minsky, but I don't have details on how it works yet.