Turing Machine and Finite State Machine Simulator

Enter the length of tape required
Enter the starting position of head
Range = [1,tape_length]
Optional - Enter intial tape contents
(use underscore for blanks)
(should be equal to tape length):
Enter tuples one in each line in the following format: current_state, read, write/move, next_state
Enter initial state:



Instructions

  1. Begin by initializing the machine.
    • Request more than the amount of tape length required. You have to start over if the head moves outside the tape.
    • Enter the starting position of the read/write head on the tape. The head should be within the tape.
    • Optionally enter the intial contents of the tape. Enter a string the same length as the tape and use underscore for blank space. For example: initializing the tape of length 5 with red starting at position 3 should be __red. Leaving this field blank creates a blank tape.
  2. Enter the tuples that define the machine, one in each line, in the following format - current_state,read,write/move,next_state. States can only be numeric. The difference between write and move is as follows:
    • /R or /r causes the tape head to move right.
    • /L and /l causes the tape head to move left.
    • All other characters are written to the tape.
  3. Enter a value for the initial state of the machine.
  4. Click "Initialize Machine".
  5. If all values entered were valid, the machine will appear on the right pane.
  6. Enter a value for the number of steps to simulate the machine and click on "Step Machine".
  7. Updating/editing the tuples at any point will be reflected the next time the machine is stepped.
  8. Enter a new tape length and head starting position and click "Initialize Machine" to start over.
  9. NOTE: If you have the tuples format correct and still get an error message, check if there is an empty line at the end
You can simulate a one-way finite state machine using this same system, by setting the third element of all tuples to /R or /L appropriately

Examples

Write StringAddition
  1. Set tape length to 10 and head position to 1. No initial contents.
  2. Enter the following tuples
    0,_,W,0
    0,W,/r,1
    1,_,H,1
    1,H,/r,2
    2,_,O,2
    2,O,/r,3
    3,_,A,3
    3,A,/r,4
    4,_,!,4
    4,!,/r,5
  3. Enter initial state as 0
  4. Click "Initialize Machine"
  5. Enter number of steps as 1
  6. Keep clicking "Step Machine" until machine completes writing the string and halts.
Quick exercise: Add another tuple to this list such that the machine does not give an error at the end of the task, but instead stays in a particular state indefinitely.

Resources

Wikipedia article on Turing Machines
Wikipedia article on Finite State Machines