• Finish up part 3 of this lab if you didn't finish it in class.
• Work on your final projects
• Review anything from modules 6 and 7 which you don't understand.

Lab 7.2 Instructions

1. Finish up Lab 7.2 from last time.

2. Create a Turing Machine that takes a unary number as input and determines if it is greater than 3. If so, the machine should put a T (for true) on the tape. If not, the machine should put an F (for false) on the tape.

      Machine    Start state    Alphabet    Format
        TM8           1         1,b,T,F     A string of ones followed by b's
   

   Here are some examples representing the numbers 4, 1, 0, 3, and 6 respectively.

      Input     Output
   
      1111bbb   1111Tbb
   
      1bbb      1Fbb
   
      bbb       Fbb
   
      111bb     111Fb
   
      111111bb  111111Tb
   

   Call one of us over and show us your TM when you have finished.

3. Create a Turing Machine which takes as input a #, followed by a string of 0's and 1's, followed by a *. The machine should reverse the string of 0's and 1's.

   Here are some examples of the TM's tape at the start and end of computation:

      Input          Output
     
      #100*bbb       #****001
   
      #1010*bb       #*****0101
   
      #1*bbbbb       #**1
   

   Here's one approach to the problem:
   1. Move right over 0's, 1's and #'s until the first * is reached. When the first * is reached, move left.

   2. Now the read-head should be scanning the first character to the left of the leftmost *. The TM should write a * over this character, move to the Right, and move into one of two possible new states, depending on whether the character just read was a 0 or a 1.

   3. Now the TM is scanning the leftmost *. Move to the right until the first b is reached. Write either a 0 or a 1 over this b (depending on what state the TM is in).

   4. Now move left until the first character to the left of the *'s is reached.
      • If this character is a #, then the TM should halt (it's done).
      • Otherwise, the TM should write a * over the character and continue with step 3.

   Call one of us over and show us your TM if you've finished. If you don't finish this TM in class, finish it for homework and show it to one of us during next lab.