Turing Machine Simulator

The program takes two command line arguments: (1) the TM description and (2) the input tape. The program halts if and when the TM halts printing out the ending state and the tape contents on halt, with head position marked.

Format of TM decription
Each state is a string of letters and numbers. Type symbols are any one letter, with the underscore representing the blank. The first line of input is of the form,

   startState haltingState1 haltingState2 ...

If the TM is accepting type (recursive), then haltingState1 is the accepting state, all other halting states reject.

Each following line is of the form, for each transition,

   delta(p,a)=(q,b)

there is a line of the form,

   P A Q B

Where P and Q are states, that is, alphanumeric strings, A is a tape symbol and B is either a tape symbol or > or <, for move right, move left, respectively.

Example:
A TM on tape symbols A, B, C and _ (the blank). Move to the first C and stop.

    start halt
    start A start >
    start B start >
    start _ start >
    start C halt C

Tape contents file
A file with the tape contents listed on many lines. Newlines are ignored and the contents are concatenated onto a single tape. Blanks are represented by the underscore (_) so that blanks in the file are ignored. Example:

   A B _ _
   _ B C A
   C

would be the tape AB___BCAC.

Assignment
After writing the simulator, write a TM to multiply two numbers Given in binary leaving the product in binary on the tape. The head begins and ends at the left end of the tape, under a blank. For exaple, 10 times 5 starts with tape,

   _1010_101
   *

where the start marks the head, and ends with,

  _110010 
  *

This gives the transition delta(s1,a)=(s2,ts).