CS3343
 Analysis of Algorithms 
  Turing Machine   
Interpreter   

Overview. Here is a simple interpreter for the Turing code. A Turing machine is encoded in the programs below as an array of pairs of ints, where the first element is the op-code of an instruction and the second element is the goto target for instructions 5 and 6. This form is neither the encoded machine as it might appear on a tape, nor the high-level version, but a convenient compromise in between. The two example machines are given as {} initializations inside the main function.

Turing Machine Interpreter
// Interpreter.java: Turing machine interp.
public class Interpreter {

   int zero;  // tape center, length=zero*2
   char[] t; // tape, not accessible by index
   int scan; // initial char being scanned
   int lc; // location counter
   int ec; // execution counter
   int offSet = 10; // dist either side of 0

   public Interpreter() {
      zero = 100;
      t = new char[zero*2];// symmetric at 0
      for (int i = 0; i < t.length; i++)
         t[i] = '0';
   }

   // for doubling program, size to double
   public void initA(int n) {
      for (int i = 0; i < n; i++)
         t[zero + i] = '1';
   }

   // for power prog, from n 1s, get 2^(n+1)
   public void initB(int n) {
      t[zero] = '1';
      for (int i = 0; i < n; i++)
         t[zero + i + 2] = '1';
   }

   public void printState(int[][] c) {
      for (int i = zero - offSet; i < zero +
            offSet; i++)
         System.out.print(t[i]);
      System.out.println(" lc:" + lc+",op:" +
         c[lc][0] + ",scan:"+scan+",ec:"+ec);
      for (int i = 0; i < scan - zero +
            offSet; i++)
         System.out.print(" ");
      System.out.println("|");
   }

   void interp(int[][] c) {
      int op; // current operator
      scan = zero;
      lc = 1;
      ec = 0; 
      while ( (op = c[lc][0]) != 4 && ec < 500) {
         ec++;
         printState(c);
         switch(op) {
            case(0):  // print 0
               t[scan] = '0'; lc++;
               break;
            case(1):  // print 1
               t[scan] = '1'; lc++;
               break;
            case(2):  // move left
               scan--; lc++;
               break;
            case(3):  // move right
               scan++; lc++;
               break;
            case(4):  // stop
               break;
            case(5):  // if 0 is scanned goto i
               if (t[scan] == '0') lc = c[lc][1];
               else lc++;
               break;
            case(6):  // if 1 is scanned goto j
               if (t[scan] == '1') lc = c[lc][1];
               else lc++;
               break;
            case(7):  // (end marker)
               break;
         } // switch
      } // while
   }

   public static void main(String[] argv) {
      // coded doubling program
      int [][] a =
        {{-1, -1},{0, 0}, {2, 0}, {6, 2},
        {1, 0}, {3, 0}, {6, 5}, {1, 0}, {3, 0},
        {6, 1}, {4, 0}, {7, 0} };
      // coded 2^(n+1) program
      int [][] b =
        {{-1, -1},{0, 0}, {2, 0}, {6, 2},
        {1, 0}, {3, 0}, {6, 5}, {1, 0}, {3, 0},
        {6, 1}, {3, 0}, {5, 22}, {3, 0}, {6, 12},
        {2, 0}, {0, 0}, {2, 0}, {6, 16}, {2, 0},
        {6, 18}, {3, 0}, {6, 1}, {4, 0}, {7, 0}};
      Interpreter in = new Interpreter();
      in.initA(4); // # of 1's initially
      in.interp(a); // run a
      // in.initB(3); // # of 1's initially
      // in.interp(b); // run b
   }
}

Representations of Turing Machines -- High-level and On Tape. The program below uses the same convenient internal representation of Turing Machines as an array of pairs on ints. It uses the same {} initialization for out two example machines. It prints this internal form in two ways: as a high-level program, and as a sequence of 0s and 1s as it would appear on a tape. The output of this program is what is used in the pictures on the main Turing Machine page.

Turing Machine Representation
// Code.java: Turing machine code
public class Code {

   String[] c = {"000", "001", "010", "011",
      "100", "101", "110", "111"}; 
   String[] p = {"print 0", "print 1",
      "move left", "move right", "stop",
      "if 0 is scanned goto ",
      "if 1 is scanned goto ", "end"};

   void printCode(int x[][]){
      for (int i = 1; i < x.length; i++){
         System.out.print(c[x[i][0]]);
         if (x[i][0] == 5) {
            System.out.print(" ");
            for (int j = 0; j < x[i][1]; j++)
               System.out.print("0");
            System.out.print(" 1");
         }
         else if (x[i][0] == 6) {
            System.out.print(" ");
            for (int j = 0; j < x[i][1]; j++)
               System.out.print("1");
            System.out.print(" 0");
         }
         System.out.println();
      }
      System.out.println();
   }

   void printProg(int x[][]){
      for (int i = 1; i < x.length; i++){
         if (i < 10) System.out.print(" ");
         System.out.print(i + ". " +
               p[x[i][0]]);
         if (x[i][0] == 5)
            System.out.print(x[i][1]);
         else if (x[i][0] == 6)
            System.out.print(x[i][1]);
         System.out.println();
      }
      System.out.println();
   }

   public static void main(String[] argv) {
      Code code = new Code();
      // coded doubling program
      int [][] a =
        {{-1,-1},{0,0}, {2,0}, {6,2},
        {1,0}, {3,0}, {6,5}, {1,0}, {3,0},
        {6,1}, {4,0}, {7,0}};
      // coded 2^(n+1) program
      int [][] b =
        {{-1,-1},{0,0}, {2,0}, {6,2},
        {1,0}, {3,0}, {6,5}, {1,0}, {3,0},
        {6,1}, {3,0}, {5,22}, {3,0}, {6,12},
        {2,0}, {0,0}, {2,0}, {6,16}, {2,0},
        {6,18}, {3,0}, {6,1}, {4,0}, {7,0}};
      code.printProg(a);
      code.printCode(a);
      code.printProg(b);
      code.printCode(b);
   }
}

Revision date: 2011-11-24. (Please use ISO 8601, the International Standard Date and Time Notation.)