Turing Machine Simulator (TMS) v1.10 documentation
The text mode Turing Machine Simulator (TMS) can be found in
/usr/ubin/sxa from any of the CS Sun4 machines. It is a replacement
for the Xturing program used in the
CS3 Computability & Intractability module
For more information on the Turing machine as a model of computation,
see
http://www.student.nada.kth.se/cgi-bin/d95-aeh/get/umeng or just
play about with TMS for a while ;-)
NOTE: There is now a manual page for tms. You can view by
typing nroff -man /usr/ubin/sxa/tms.1
To run TMS, use the command:
/usr/ubin/sxa/tms machine.tm
where machine.tm is the name of your Turing machine in
the same format as the Xturing input file. More details can be found in
the Xturing documentation (this is a DVI file). The program will
then prompt you for the input tape, which you can type at the
keyboard, or pipe in from a text file like this:
/usr/ubin/sxa/tms machine.tm < tape.tp
Simulation Speed
If you want to change the speed of the output, then give the -d (Delay)
parameter, this allows you to change the delay between each iteration to a
specific amount (Specified in 1/100s intervals). For example, the following
line will give a delay of 1 second between each iteration (The default value is
50 which corresponds to half a second. If you don't want any delay,
use -d0 to run the simulation at full speed.
You can specify a -s option to run the first part of the
simulation at full speed, but from a specified step, run it at the
delayed speed. This is useful for debugging your Turing machines when
the problem is not at the start of the simulation. Give the step
number in the parameter. For example, the following line will display
the first 230 steps at full speed, then wait for half a second
between all subsequent steps:
/usr/ubin/sxa/tms machine.tm -d50 -s230
If you don't want an automatic delay, you can use the -m
(manual) option, so that each iteration will take place only when you
press return. This won't work if you redirect a tape into the
program.
Output modes
There are two terse output modes, -t (Terse) and -T (Very
terse). -t displays each of your states as a number (It reduces the
output width, so as to prevent word-wrap), and -T doesn't display the
transitions at all, only the tape output.
If you want to limit the output to the printing transitions only then use
the -x parameter.
To produce output which is similar to the output produced by the
XTuring program, use the -c (Compatibility) switch. This also
implies that you only want to display printing transitions, so if you
want to use the compatibility mode and display all
transitions (It'll be long though) then use -cx
To display each transition in the same line (Each overwriting the previous
one) then use the -r (Return only) option.
Combining options
All of the above options can be combined, so for example, to run the
simulation quickly, all on one line, and only display printing transitions,
use the following :
/usr/ubin/sxa/tms machine.tm -d2 -r -x
or even:
/usr/ubin/sxa/tms machine.tm -d2rx
Known problems/limitations
If any of the limitations cause a problem, let me know and I'll change
them.
- There is a maximum limit of 100 states
- There is a maximum limit of 255 Transition rules
- You can't use commas in symbols or state names - not that you'd want to
:-)
- The tape cannot be longer than 1024 characters.
- The program isn't completely idiot-proof - it may be possible
to crash TMS by giving it complete gibberish in the input. Most problems
will be caught, many will just result in a warning. If you have an
input file which causes TMS to crash, let me know.
Differences between tms -c and XTuring
- TMS includes the blank symbol in the initial tape alphabet, XTuring
does not.
- TMS may put 'extra' blank characters on the end of a line relative to
XTuring.
- The summary at the end of the output is different.
Bug fixes/Modifications since GA
- Version 0.5
- No longer Segmentation faults if an undefined state is referenced
- Now warns user if an undeclared symbol is referenced
- Version 1.0
- User interface rewritten, now has more options
- It now updates the final state correctly.
- Version 1.01
- Now allows blank symbols in the middle of the tape
- Version 1.10
- Changed the display so longer tapes look better
- Increased maximum tape length to 1024
- NOTE : The old version is still available as
/usr/ubin/sxa/tms101
- The machine definition file can now have the values of
Q, I, F, G, S and D in any order
- Added the -c switch to produce XTuring compatible output
Future plans (Yeah, right...)
- Write some more complete documentation
- Clean up the code so that I can distribute it
- Re-code it in Java (Ha!)
If you have any other suggestions for future versions of TMS, let me
know.
Please address all comments/bug reports to
sxa@dcs.ed.ac.uk