/*
  Interpreter of the Turing Machine.
  An initial CURRENT_STATE of the Turing Machine is coded by "start",
  final CURRENT_STATE - by "stop".
  The shift of the head to the right is designated through "right",
  to the left - through "left" .
*/

class tmmul2 {

    public static int ltape=4400;  /* Length of a tape  */
    public static int nunits=2000; /* Quantity of units, not of zero */
    public static int head;
    public static String state;

    /* Indexes in array of the instructions,   */
    public static final int CURRENT_STATE  = 0;
    public static final int CURRENT_SYMBOL = 1;
    public static final int NEXT_SYMBOL    = 2;
    public static final int NEXT_STATE     = 3;
    public static final int MOVE           = 4;

    public static String[] tape = new String[ltape];

    public static final String[][] instruction = {
        { "start",  " ",  " ",  "stop" ,  "right" },
        { "start",  "2",  "2",  "start",  "right" },
        { "start",  "1",  "2",  "b"    ,  "left"  },
        { "b"    ,  "2",  "2",  "b"    ,  "left"  },
        { "b"    ,  " ",  "2",  "start",  "right" }
    };

    public static void main (String args[]) {
        head = ltape/2;     /* the head in the middle of a tape  */
        for (int i = 0; i < ltape; i++)      /* filling of blank  */
            tape[i] = " ";
        for (int i = head; i < head+nunits; i++)
            tape[i] = "1";
        long start = System.currentTimeMillis();

        test();

        long end = System.currentTimeMillis();
        System.out.println("Total time = "+ (end-start)*0.001);
        System.out.println("Final Tape : " );
        for (int i = 0; i < ltape; i++)
            System.out.print(tape[i]) ;
    }


    public static void test() {
        state = "start";
        while (state != "stop") {
            for (int i=0; i<instruction.length; i++) {
                if (state == instruction[i][CURRENT_STATE]
                && tape[head] == instruction[i][CURRENT_SYMBOL]) {
                    state=instruction[i][NEXT_STATE];
                    tape[head]=instruction[i][NEXT_SYMBOL];
                    if(instruction[i][MOVE]=="right") head++;
                    if(instruction[i][MOVE]=="left" ) head--;
                }
            }
        }
    }
}