Virtual Turing Machine (VTM)
This page is a mirror of Paul Ming's VTM page, and was created to reduce the burden on Paul's server.
What is a Turing Machine?
Alan Turing was a cryptographer. He helped Britain break the German
Enigma machines in WWII. He also invented a concept of a type of
computer, called a "Turing Machine." Theoretically, a Turing machine is
just as powerful as any other computer. Conceptually, a Turing Machine
has a finite set of states, a finite alphabet (that has a blank symbol),
and a finite set of instructions. Physically, it has a head that can read,
write, and move along an infinitely long tape that is divided into cells,
where each cell has a value of blank or a letter in the Turing Machine's
alphabet. An instruction is defined as a five tuple, like this:
(starting state, starting value, new state, new value, movement)
The starting state is the state the head is currently in. The starting
value is the value of the cell the head is positioned at. The new state
and new value replace the starting state and starting value, respectively.
The movement specifies which direction the head moves by one cell. The
head halts when it can not find an instruction for the current state or
the current cell value. A Turing machine will start at the first
non-blank cell.
Usually, states are named s0, s1, s2, etc. The
alphabet is usually 'B', for blank, and '1' and '0'. Numbers can (but not
necessarily) be represented by a series of 1s with a length of n +
1 for a number n.
Syntax of the Virtual Turing Machine
- The Input Tape
-
Type in what you want the tape to look like when you first start. See
"Cell values" below for what can go in a tape. An example is
'BB11111BB'.
- Blank character
-
Type in the character that represents the blank character here. I would
recommend 'B' for blank characters. See "Cell values" below for valid
characters. If the VTM can't find a non-blank character to start at, it
will start in the middle of the tape.
- The Initial State
-
The initial state field is just the name of the state that the machine
should start out in. See "States" below for valid state names.
- Instructions
-
Instructions are in the form of:
starting_state, starting_value, new_state, new_value, movement
Spaces and tabs do not matter, as long as there a comma between each field.
Instructions can not span over multiple lines. Blank lines are ignored.
Here's an example set of instructions:
s0, 1, s0, 1, R # this line skips over a series of 1s
s0, 0, s1, 1, R # this line changes state to 's1' and
# the cell value to '1' when the
# machine encounters an '0' while
# it's in state 's0'
- Notice that there isn't a 's1' state. That means the machine will halt no
matter what value it encounters once it's in state 's1'. So 's1' is
called a "stopping state." You may want to name your stopping state
'halt' or 'stop'. The VTM will stop once it tries to past the beginning
or the end of the tape.
The order of the instructions do not matter (unless you have two
instructions defined for state/cell value, in which case the VTM will use
the last instruction).
- Comments
-
Comments start with the pound character ("#"). Everything on the line
after the pound character is ignored.
- States
-
States' names consist of letters, digits, and the underscore character
("_"). Some valid names are 'New_Mexico', 's0', '_', 'stop', '6', and
'initState'. States are case sensitive, so 'foo' and 'Foo' are two
different states.
- Cell values
-
Cell values are one letter, digit, or underscore long. So 'A' is a
valid value, and 'AA' is invalid (it would be considered two cells). Like
states, cell values are case sensitive.
- Movement
-
Movement is either right or left. Right is represented by a plus sign
("+"), or an uppercase or lowercase 'R'. Left is represented by a minus
sign ("-"), or an uppercase or lowercase 'L'. You need not be consistent,
although it looks nicer that way.
- Executing
-
Output can be the final result of the tape, a single line of output for
every step the VTM goes through, or two lines per step. The last two ways let
you see what the VTM does. Showing states outputs the state after the tape
every time the tape is shown. The last option allows you to show the
form (with your script and initial values in it) again either at the top,
bottom, or not at all.
- Saving
-
Saving will take your script and initial values, and spit them back out to
you as the default values for the fields. You can then save the returned
file on your computer with your browser. Most people will want to go to
'File' to 'Save As...'. Just open up that saved file in your browser and
you'll have your script. Of course, you can do this with scripts you just
executed (and you'll have the results saved too).
The VTM
Get the Perl script from Paul Ming