Examples of tm runs

Sample TM Runs

David S. Woodruff

You will find it useful to run TM as you read these examples.

Getting Started. A very simple example done two ways.
Tracing the Machine Execution. Two methods are available for watching the machine run step by step.
Using Comments. Comments may be added to any TM command line using '#'.
Using the Help Facility. Showing how the help facility works.
Reading and Using .tm Files. Quintuple lists may be stored in files.
Debugging Tools. You can set 'break points' and 'watch points' to look for errors in your quintuple lists

Getting Started

In this first example we create a tape then create and run a set of quintuples that change all 1's to 0's on a tape.

	#./tm
        	     TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> set tape 1111
	tm> add quint 0100r
	tm> go
	Halted.  State is 0
	tm> show tape
	0000	
	    ^
	tm> exit
	#

The carot, '^', shows the location of the tape head. Let's do it again showing how commands can be entered in a flexible way.

	# ./tm
	             TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> set tape 111 show tape
	111
	^
	tm> add quint 0100r
	tm> go, show tape
	Halted.  State is 0
	000
	   ^
	tm> exit

Notice that commands may be 'strung together'. Commas have no effect. They simply make the lines easier to read.

Tracing the Machine Execution

You can 'set trace tape' to display the tape at each step, or you can 'set trace descriptor' to display the machine descriptor at each step. You can stop the display by entering 'set trace tape'.

	#./tm
	             TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> set tape 1111
	tm> add quint 0100r
	tm> set trace tape
	tm> go
	1111
	^
	    state: 0,  next quint: 0100R
	0111
	 ^
	    state: 0,  next quint: 0100R
	0011
	  ^
	    state: 0,  next quint: 0100R
	0001
	   ^
	    state: 0,  next quint: 0100R
	0000
	    ^
	    state: 0,  next quint: (none)
	Halted.  State is 0
	tm> set tape 1111
	tm> set trace descriptor
	tm> go
	(,0,1111) -> (0,0,111) -> (00,0,11) -> (000,0,1) -> (0000,0, ) ->
	Halted.  State is 0
	tm> exit
	#

Using Comments

Let's add some comments while we work.

	#./tm
	             TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> # this is a comment.
	tm> # first we create a tape
	tm> set tape 111
	tm> # now let's show the tape
	tm> show tape
	111
	^
	tm> # now create a quintuple that changes all the 1's to 0's
	tm> # we will enter 0100r when prompted...
	tm> add quint
	enter quintuple (string): 0100r
	tm> # now run the turing machine
	tm> go
	Halted.  State is 0
	tm> # now let's see the tape again
	tm> show tape
	000
	   ^
	tm> # the carot, '^', shows where the tape head is.
	tm> # Now we quit the session
	tm> exit
	#

Using the Help Facility

TM has a useful 'help' facility. Let's suppose that we wish to 'add' a quintuple, but by accident we try to 'set' a quintuple instead. We will use the help facility to work our way to the correct procedure.

  # ./tm
               TM --  Turing machine program.  V1.32
      Enter 'help' for help.
  tm> set tape 111
  tm> set quint 0100r
  invalid or ambiguous set command ->  quint
  set what?      # So 'quint' is not acceptable.  What is acceptable?
  set what? ?    # I enter ? to get some help

  (Press 'enter' to exit or to see last item)
  **** TM SET ****
        Set a machine characteristic.

  -----additional help available for:
         TRACE     DEBUG     DISPLAY   MACRO     MAX_STEP  TAPE      STATE
         SYMBOL    COMMENT   WATCH     BREAK     EXIT      QUIT
  subtopic?>
  set what? # I pressed 'return' to get out of help.  QUINT is not 
  set what? # a thing that can be 'set'
  set what? exit   # 'exit' returns from 'set what?' prompt.  ^D also works.
  tm> # I will enter 'help' to get to the main help menu
  tm> help

  (Press 'enter' to exit or to see last item)
  **** TM ****
    turing machine interpreter

  -----additional help available for:
         EXIT      QUIT      ADD       ENTER     DELETE    #         SHOW
         LIST      EDMACRO   GO        MOVE      READ      WRITE     RUN
         SAY       ECHO      STEP      SET       CANCEL    QUINTUPLE_LISTS
         ENTERING_COMMANDS   USING_MACROS        DEBUG_MODE
         BREAK_POINTS        WATCH_POINTS        WRITTEN_BY
  subtopic?> add

  (Press 'enter' to exit or to see last item)
  **** TM ADD ****
        add a new quintuple to the quintuple list.
           e.g.,  'add quint 0110r'

  subtopic?> 
  subtopic?>

  **** TM ****

  -----additional help available for:
         EXIT      QUIT      ADD       ENTER     DELETE    #         SHOW
         LIST      EDMACRO   GO        MOVE      READ      WRITE     RUN
         SAY       ECHO      STEP      SET       CANCEL    QUINTUPLE_LISTS
         ENTERING_COMMANDS   USING_MACROS        DEBUG_MODE
         BREAK_POINTS        WATCH_POINTS        WRITTEN_BY
  subtopic?>
  tm> # don't use comments while in the 'help' facility
  tm> # return from 'subtopic?' by pressing 'return'
  tm> add quint 0110r
  tm> exit
  #

Reading and Using .tm Files

A .tm file consists of comments and quintuples for some turing machine. In order to use it, it must be in your default directory. See the documentation for the format of .tm files.

Here is an example. We will print it ('cat'), read it into TM, then use it on a couple of tapes.

	# cat paren.tm
	This is a well-formed parentheses string checker.
	Adopted from Prather, page 481.  (Note that the left parenthesis
	has three contexts in this file.)

	(0((0R
	(0)A1L
	(0AA0R
	(0  2L
	(1(A0R
	(1AA1L
	(1  NR  Prather has 0 instead of R
	(2((NR  Prather has 0 instead of R
	(2AA2L
	(N--NR  Never used.  Its existence forces N to be a non-final state.
	(2  YR
	#./tm
	             TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> read tm paren
	tm> set tape ((()))
	tm> go
	Halted in final state Y
	tm> set tape ((())
	tm> go
	Halted.  State is N
	tm> exit
	#

Note that in the example, 'Y' is used to signal balanced parentheses, 'N' to signal unbanlanced parentheses.

.tm files may be written out from TM as well as read in.

Debugging Tools

We will read the same .tm file as in the last example and illustrate some debugging techniques.

	# ./tm
	             TM --  Turing machine program.  V1.32
	    Enter 'help' for help.
	tm> read tm paren
	tm> list
	0((0R
	0)A1L
	0AA0R
	0  2L
	1(A0R
	1AA1L
	1  NR
	2((NR
	2AA2L
	N--NR
	2  YR
	tm> # when a tm file is read the comments are dropped.
	tm> help set break

(Press 'enter' to exit or to see last item)
**** TM SET BREAK ****
          Usage:  'set break (quintuple)', where (quintuple) is a two-symbol
      string designating a quintuple.  The turing machine will stop if the
      next instruction will use this quintuple.
          To move past a break point, 'step' a single time, or 'set debug off'

	subtopic?>
	tm> set break 1a
	no quintuple with that initial state has that initial symbol.
	tm> set break 1A
	tm> # quintuples are case sensitive.
	tm> set tape ((()))
	tm> go
	halted at break point.
	tm> show tape
	((AAA)
	   ^
	tm> show next   # shows the next quintuple to be executed
	1AA1L
	tm> step
	tm> show tape show next
	((AAA)
	  ^
	1AA1L	
	tm> go
	halted at break point.
	tm> show tape show next
	((AAA)
	  ^
	1AA1L
	tm> show break
	breaks are set for quintple(s):
	         (1,A,A,1,L)
	tm> cancel break 1A
	tm> go
	Halted in final state Y
	tm> exit
	#

You can also set 'set watch' on a state or a symbol so that execution halts when either is about to change. To get past the watch point you must enter 'step' or 'set debug off'

David S. Woodruff
MIT Lab for Nuclear Science
Suffolk University, Math and Computer Science
davewoodr@aol.com