CSE 111, Fall 2004

Karel the Robot as a Turing Machine

Last Update: 7 December 2004

Note: NEW or UPDATED material is highlighted


  1. A Turing Machine consists of:

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

  2. Karel the Robot can simulate a TM as follows:

  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. NEW Lopa Mukherjee's Karel-as-TM Powerpoint slide show



Copyright © 2000-2004 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 111F04/karel-as-TM-2004-12-07.html