virtual turing machine

The YML Virtual Turing Machine (yvtm).

It takes as input a YML description of a turing machine, run that machine, and then output the result.

Here's an example of a .yvtm source file for the 3 state busy beaver .

 # busybeaver3.yvtm
 tape:    "0"
 start:   one
 blank:   "0"
 accept:  []
 reject:  []

 machine:

 #      current  read     next      write   move
 #      state    symbol   state     symbol  to
 #      -----    ------   --------  -----   -----

    - [ one,     0,       two,      1,      right ]
    - [ one,     1,       HALT,     1,      right ]

    - [ two,     0,       three,    0,      right ]
    - [ two,     1,       two,      1,      right ]

    - [ three,   0,       three,    1,      left  ]
    - [ three,   1,       one,      1,      left  ]

There are libraries to process YAML in most modern languages. For example, to read this YAML into a python program, all you would need is

import yaml
turing = yaml.load(open('busybeaver3.yvtm'))

which would give you this data structure

    turing = {'tape'   : '0',
              'accept' : [],
              'reject' : [],
              'blank'  : '0',
              'machine': [['one',   0, 'two',   1, 'right'],
                          ['one',   1, 'HALT',  1, 'right'],
                          ['two',   0, 'three', 0, 'right'],
                          ['two',   1, 'two',   1, 'right'],
                          ['three', 0, 'three', 1, 'left'],
                          ['three', 1, 'one',   1, 'left']]
             }

(Note: YAML will put bare words into quote strings. However, it will also convert bare numbers into number by default, so you will need to be a bit careful with symbols like 0 and convert them appropriately.)

The output of yvtm should be either the full history of the turing simulation, or just the last tape and state.

For example, here's what running my yvtm.py looks like.

   $ python yvtm.py -help
   yvtm.py : YAML Virtual Turing Machine in python 
   Usage: python yvtm.py [-quiet] [-help] [-tape=...] filename.yvtm 

   $ python yvtm.py -quiet busybeaver3.yvtm 
      1  1  1 <1> 1  1  : HALT

   $ python yvtm.py busybeaver3.yvtm
   <0> : one
    1 <0> : two
    1  0 <0> : three
    1 <0> 1  : three
   <1> 1  1  : three
   <0> 1  1  1  : one
    1 <1> 1  1  : two
    1  1 <1> 1  : two
    1  1  1 <1> : two
    1  1  1  1 <0> : two
    1  1  1  1  0 <0> : three
    1  1  1  1 <0> 1  : three
    1  1  1 <1> 1  1  : three
    1  1 <1> 1  1  1  : one
    1  1  1 <1> 1  1  : HALT
   ** HALT **  (No matching rule)    

After giving you a chance to write something that implements this, I'll upload mine.

• more examples ... including Jim's yvtm.py simulator