Homework 6 aka Exam 3

Coding Part

1. Write a Python program to implement a Turing Machine (TM) simulator.
2. Write a Python program to implement a Random Access Machine (RAM) simulator.

Non-coding Part

1. Design a TM that performs the "div" operation on "unary" numbers and test it under the TM Simulator. Here are some sample runs:

   ASCSC1PP629W1:hw6 raj$ python3 TM.py div.tm saaaaaaadaaa=
   Initial Tape:
   saaaaaaadaaa= 1
   ^
   Final Tape:
   saaaaaaadaaa=aa h
                ^
   ACCEPT
   
   ASCSC1PP629W1:hw6 raj$ python3 TM.py div.tm saaaaaaadaaaa=
   Initial Tape:
   saaaaaaadaaaa= 1
   ^
   Final Tape:
   saaaaaaadaaaa=a h
                 ^
   ACCEPT
   
   ASCSC1PP629W1:hw6 raj$ python3 TM.py div.tm saadaaaa=
   Initial Tape:
   saadaaaa= 1
   ^
   Final Tape:
   saadaaaa=# h
            ^
   ACCEPT
   ASCSC1PP629W1:hw6 raj$
   

2. Write a RAM program to check if a positive number is prime. The input number is assumed to be in register R1 when the program starts running and the result, 1 if input number is a prime and 0 if the input number is not a prime is placed in register R1 at the end. Run the program under the RAM Simulator and verify your program. Here are some sample runs:

   ASCSC1PP629W1:hw6 raj$ python3 RAM.py prime.ram 
   Input:
   R1 ==> 18
   R2 ==> 0
   R3 ==> 0
   R4 ==> 0
   
   
   Output:
   R1 = 0
   
   ASCSC1PP629W1:hw6 raj$ python3 RAM.py prime.ram 
   Input:
   R1 ==> 499
   R2 ==> 0
   R3 ==> 0
   R4 ==> 0
   
   
   Output:
   R1 = 1
   ASCSC1PP629W1:hw6 raj$ 
   

3. The following problems have to do with encoding and decoding of TMs.

   1. Encode the following TMs and determine if their codes are in ALAN or not:

      TM 1:
      
      1,3,a,#,r
      3,1,b,$,l
      3,4,#,a,r
      
      TM 2:
      
      1,2,#,$,r
      1,3,a,#,r
      1,3,b,#,r
      3,1,#,a,l
      3,3,a,#,r
      3,3,b,#,r
      

   2. Decode the following code words from CWL and determine if they belong to ALAN or not.

      • abaaabaaabaaaabaababbab

      • abaabaabba