Saturday, 21 December 2013

Turing Machine

Problem:

Design a TM to perform addition of 2 integers.

Background:

I am using TM with one way infinite tape

Time Complexity (for compute function):

O(m) where m is no1+no2
no1 is 1st operand for addition & no2 is second

Code:



import java.util.Scanner;

public class Adder {

 int head,sum;
 char[] tape;
 
 void init( ) {
  //one way infinite tape 
  tape = new char[37677];
  for (int i = 0; i < tape.length; i++) {
   tape[i] = 'B';
  }
  Scanner s = new Scanner(System.in);
  System.out.println("enter no1");
  int no1 = s.nextInt();
  System.out.println("enter no2");
  int no2 = s.nextInt();
  int p = 0;
  for (int i = 0; i < no1; i++,p++) {
   tape[i] = '0';
   
  }
  tape[p] = '1';
  p++;
  for (int i = 0; i < no2; i++,p++) { 
   tape[p] = '0';
  }
  compute();
 }
 private void compute() {
  // TODO Auto-generated method stub
  for (int i = 0; i < tape.length; i++) {
   if(tape[i] == '1') {
    tape[i] = '0';
   }
   if(tape[i] == 'B')
    reverse(i);
  }
 }
 
 private void reverse(int i) {
  // TODO Auto-generated method stub
  --i;
  tape[i] = 'B';
  for (int j = 0; j < tape.length; j++) {
   if(tape[j] != 'B')
    sum++;
  }
  System.out.println("sum is = " + sum);
  System.exit(0);
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new Adder().init();
 }

}