Karel the Robot as a Turing Machine

1. A Turing Machine consists of:
   • an arbitrarily long (i.e., unbounded, or infinite) tape, divided into squares
     (think of a roll of toilet paper :-)

   • such that each square either is blank or has a 0 or a 1 on it

   • with 5 basic instructions (actions):
     • move-left
     • move-right
     • print-1
     • print-0
     • erase

     which can be combined by sequence, selection (if-then-else), and repetition (while-loop).

   There are other ways to characterize TMs. For more information, see:

   • "Great Idea [of Computer Science] II: Turing Machines"

2. Karel the Robot can simulate a TM as follows:
   • restrict Karel to moving along 1st St. and to moving up and down 1st. Ave.;
     this basically represents the 1-dimensional TM tape as if bent at right angles

   • assume that Karel has an arbitrarily large (i.e., unbounded, or infinite) supply of beepers

   • blank = no beeper on corner
     1 = 1 beeper on corner
     0 = 2 beepers on corner

3. //Karel as Turing Machine; written by Lopa Mukherjee
   beginning-of-program
      //------------------------------------------------------------------------------------------------------
      // beginning of some generic instruction definitions that help Karel to move around
      // in his world 
      
      define-new-instruction turnaround as
      begin
         turnleft;
         turnleft;
      end;
      
      define-new-instruction face-south as
         while not-facing-south do
            turnleft;
      
      define-new-instruction face-north as
         while not-facing-north do
            turnleft; 
      
      define-new-instruction face-east as
         while not-facing-east do
            turnleft; 
      
      define-new-instruction face-west as
         while not-facing-west do
            turnleft;
      
      define-new-instruction pickallbeeper as
         while next-to-a-beeper do
            pickbeeper;
      
      define-new-instruction move-right-without-putting-beeper as
      begin
         face-south;
         if front-is-clear then 
            move
         else 
         begin
            face-east;
            move
         end
      end; 
      
      define-new-instruction move-left-without-putting-beeper as
      begin
         face-west;
         if front-is-clear then
            move
         else
         begin
            face-north;
            move
         end
      end; 
      
      //---------------------------------------------------------------------------------------------------------------------
      // beginning of instruction definitions that help Karel to emulate the 
      // Turing machine
      
      define-new-instruction move-right as
      begin
         face-south;
         if front-is-clear then 
            move
         else 
         begin
            face-east;
            move
         end;
         if not-next-to-a-beeper then
         begin
            putbeeper;
            putbeeper
         end 
      end; 
      
      define-new-instruction move-left as
      begin
         face-west;
         if front-is-clear then
            move
         else
         begin
            face-north;
            move
         end;
         if not-next-to-a-beeper then
         begin
            putbeeper;
            putbeeper
         end     
      end; 
      
      define-new-instruction erase as
      begin
         move-left-without-putting-beeper;
         if not-next-to-a-beeper then
         begin
            move-right-without-putting-beeper;
            pickallbeeper;
            move-right-without-putting-beeper       
         end
         else
         begin
            move-right-without-putting-beeper;
            move-right-without-putting-beeper;
            if not-next-to-a-beeper then
            begin
               move-left-without-putting-beeper;
               pickallbeeper;
               move-left-without-putting-beeper       
            end
            else
               move-left-without-putting-beeper
         end
      end;
      
      define-new-instruction print-1 as
      begin
         pickallbeeper;
         putbeeper;
      end; 
      
      define-new-instruction print-0 as
      begin
         pickallbeeper;
         putbeeper;
         putbeeper
      end; 
      //--------------------------------------------------------------------------------------------------------------- 
      // program to emulate the flow chart for negation
      //i/p : 1 square
      //o/p : 2 square
      
      beginning-of-execution
         if next-to-a-beeper then
         begin
            pickbeeper;
            if next-to-a-beeper then
            begin
               putbeeper;
               move-right;
               print-1
            end     
            else    
            begin
               putbeeper;
               move-right
            end     
         end;              
         turnoff;
      end-of-execution
   end-of-program
   

4. Lopa Mukherjee's Karel-as-TM Powerpoint slide show