/*
  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 tmdiv3 {

    public static int ltape=50;  /* Length of a tape  */
    public static int nunits=20; /* 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",  "0", "0", "start",  "right" },
        { "start",  "1", "1", "q1",     "right" },
        { "start",  "2", "2", "q2",     "right" },
        { "start",  "3", "3", "start",  "right" }, 
        { "start",  "4", "4", "q1",     "right" },
        { "start",  "5", "5", "q2",     "right" },
        { "start",  "6", "6", "start",  "right" },
        { "start",  "7", "7", "q1",     "right" }, 
        { "start",  "8", "8", "q2",     "right" },
        { "start",  "9", "9", "start",  "right" },
        { "start",  " ", " ", "q0stop", "right" },
        { "q1",     "0", "0", "q1",     "right" },
        { "q1",     "1", "1", "q2",     "right" }, 
        { "q1",     "2", "2", "start",  "right" },
        { "q1",     "3", "3", "q1",     "right" }, 
        { "q1",     "4", "4", "q2",     "right" }, 
        { "q1",     "5", "5", "start",  "right" },
        { "q1",     "6", "6", "q1",     "right" },
        { "q1",     "7", "7", "q2",     "right" },
        { "q1",     "8", "8", "start",  "right" },
        { "q1",     "9", "9", "q1",     "right" },
        { "q1",     " ", " ", "q1stop", "right" },
        { "q2",     "0", "0", "q2",     "right" },
        { "q2",     "1", "1", "start",  "right" }, 
        { "q2",     "2", "2", "q1",     "right" },
        { "q2",     "3", "3", "q2",     "right" },
        { "q2",     "4", "4", "start",  "right" },
        { "q2",     "5", "5", "q1",     "right" },
        { "q2",     "6", "6", "q2",     "right" },
        { "q2",     "7", "7", "start",  "right" },
        { "q2",     "8", "8", "q1",     "right" },
        { "q2",     "9", "9", "q2",     "right" },
        { "q2",     " ", " ", "q2stop", "right" },
        { "q0stop", " ", "0", "stop",   "right" }, 
        { "q1stop", " ", "1", "stop",   "right" }, 
        { "q2stop", " ", "2", "stop",   "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] = "8";
        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--;
                }
            }
        }
    }
}