One of the foundational mathematical constructs behind computer science
is the universal Turing Machine.



(Alan Turing introduced the idea of such a machine in 1936–1937.)

Indeed one way to definitively prove that a language
is turing-complete
is to implement a universal Turing machine in it.



Task

Simulate such a machine capable
of taking the definition of any other Turing machine and executing it.

Of course, you will not have an infinite tape,
but you should emulate this as much as is possible.

The three permissible actions on the tape are "left", "right" and "stay".

To test your universal Turing machine (and prove your programming language
is Turing complete!), you should execute the following two Turing machines
based on the following definitions.


Simple incrementer

 States: q0, qf
 Initial state: q0
 Terminating states: qf
 Permissible symbols: B, 1
 Blank symbol: B
 Rules:
 (q0, 1, 1, right, q0)
 (q0, B, 1, stay, qf)


The input for this machine should be a tape of 1 1 1


Three-state busy beaver

 States: a, b, c, halt
 Initial state: a
 Terminating states: halt
 Permissible symbols: 0, 1
 Blank symbol: 0
 Rules:
 (a, 0, 1, right, b)
 (a, 1, 1, left, c)
 (b, 0, 1, left, a)
 (b, 1, 1, right, b)
 (c, 0, 1, left, b)
 (c, 1, 1, stay, halt)


The input for this machine should be an empty tape.


Bonus:

5-state, 2-symbol probable Busy Beaver machine from Wikipedia

 States: A, B, C, D, E, H
 Initial state: A
 Terminating states: H
 Permissible symbols: 0, 1
 Blank symbol: 0
 Rules:
 (A, 0, 1, right, B)
 (A, 1, 1, left, C)
 (B, 0, 1, right, C)
 (B, 1, 1, right, B)
 (C, 0, 1, right, D)
 (C, 1, 0, left, E)
 (D, 0, 1, left, A)
 (D, 1, 1, left, D)
 (E, 0, 1, stay, H)
 (E, 1, 0, left, A)


The input for this machine should be an empty tape.

This machine runs for more than 47 millions steps.




/*REXX program executes a  Turing machine  based on   initial state,  tape, and rules.  */
state = 'q0'                                     /*the initial Turing machine state.    */
term  = 'qf'                                     /*a state that is used for a  halt.    */
blank = 'B'                                      /*this character is a  "true"  blank.  */
call Turing_rule  'q0 1 1 right q0'              /*define a rule for the Turing machine.*/
call Turing_rule  'q0 B 1 stay  qf'              /*   "   "   "   "   "     "      "    */
call Turing_init   1 1 1                         /*initialize the tape to some string(s)*/
call TM                                          /*go and invoke the  Turning  machine. */
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
TM:  !=1;   bot=1;   top=1;   @er= '***error***' /*start at  the tape location   1.     */
     say                                         /*might as well display a blank line.  */
          do cycle=1  until  state==term         /*process Turing machine  instructions.*/
             do k=1  for rules                   /*   "       "       "        rules.   */
             parse var rule.k rState rTape rWrite rMove rNext .          /*pick pieces. */
             if state\==rState | @.!\==rTape  then iterate               /*wrong rule ? */
             @.!=rWrite                          /*right rule;  write it ───► the tape. */
             if rMove== 'left'  then !=!-1       /*Are we moving left?   Then subtract 1*/
             if rMove=='right'  then !=!+1       /* "   "    "   right?    "    add    1*/
             bot=min(bot, !);   top=max(top, !)  /*find the  tape  bottom and top.      */
             state=rNext;       iterate cycle    /*use this for the next  state;  and   */
             end   /*k*/
          say @er 'unknown state:' state;  leave /*oops, we have an unknown state error.*/
          end   /*cycle*/
     $=                                          /*start with empty string  (the tape). */
          do t=bot  to top;        _=@.t
          if _==blank  then _=' '                /*do we need to translate a true blank?*/
          $=$ || pad || _                        /*construct char by char, maybe pad it.*/
          end   /*t*/                            /* [↑]  construct  the  tape's contents*/
     L=length($)                                 /*obtain length of  "     "       "    */
     if L==0     then $= "[tape is blank.]"      /*make an  empty tape  visible to user.*/
     if L>1000   then $=left($, 1000) ...        /*truncate tape to 1k bytes, append ···*/
     say "tape's contents:"  $                   /*show the tape's contents (or 1st 1k).*/
     say "tape's   length: " L                   /*  "   "     "   length.              */
     say 'Turning machine used '    rules    " rules in "    cycle    ' cycles.'
     return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Turing_init:  @.=blank;  parse arg x;    do j=1  for words(x);  @.j=word(x,j);  end  /*j*/
              return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Turing_rule:  if symbol('RULES')=="LIT"  then rules=0;       rules=rules+1
              pad=left('', length( word( arg(1),2 ) ) \==1 )          /*padding for rule*/
              rule.rules=arg(1);         say right('rule' rules, 20)   "═══►"   rule.rules
              return