Virtual Turing Machine (VTM)

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:

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 s₀, s₁, s₂, 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