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.




 
[Attempt at Turing machine for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
 
[Library subroutine M3 prints header and is then overwritten.]
            PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
            *!!NR!STEPS@&#..PZ [..PZ marks end of header]
 
            T48K    [& (delta) parameter: Turing machine tape.]
            P8F     [Overwrites most of initial orders.]
 
            T50K    [X parameter: once-only code.]
            P100F   [Gets overwritten by the Turing machine tape.]
 
[Put the following as high in memory as possible,
 to make room for the Turing machine tape.]
            T52K    [A parameter: rules and initial pattern. Also marks end]
            P781F   [of Turing tape, so must go immediately after tape area.]
 
            T55K    [V parameter: program-wide variables.]
            P810F   [Even address, 9 locations]
 
            T46K    [N parameter: constants.]
            P820F   [Even address]
 
            T47K    [M parameter: main routine.]
            P859F
 
            T51K    [G parameter: library subroutine P7]
            P988F   [Even address, 35 locations.]
 
[============================= A parameter ===============================]
            E25K TA GK
      [0] [End of Turing tape area]
[Comment-in the desired task, or add another (2 symbols only).]
[Counts are stored in the address field.]
[Each rule is defined by an EDSAC pseudo-order, as follows:
   Function letter: L = left, R = right, S = stay
   Address field = new state number
   Code letter: F if new symbol = 0, D if new symbol = 1.
 No rule is needed for the halt state.]
      [0]
[Simple incrementer: states are q0 = 0, qf = halt = 1
            P1F     [1 state, excluding the halt state
            S1D RD  [2 rules for each state (symbols 0 and 1)
            P1F     [1 word in tape area to be initialized
            PF P3D  [location 0 relative to tape, init to 7]
[3-state busy beaver: states are a = 0, b = 1, c = 2, halt = 3]
            P3F     [3 states, excluding the halt state]
            R1D L2D [2 rules for each state (symbols 0 and 1)]
            L0D R1D
            L1D S3D
            PF      [0 words to be initialized (start with empty tape)]
[5-state busy beaver: states are A = 0, ..., E = 4, halt = 5
            P5F     5 states, excluding the halt state
            R1D L2D 2 rules for each state (symbols 0 and 1)
            R2D R1D
            R3D L4F
            L0D L3D
            S5D L0F
            PF      0 words to be initialized (start with empty tape)]
 
[============================= X parameter ===============================]
            E25K TX GK
[The following once-only code is loaded into the Turing machine tape area.]
[It runs at start-up, then gets overwritten when the tape is cleared.]
[Enter with acc = 0.]
      [0]   T2V     [initial state assumed to be state 0]
            T3V     [tape head starts at position 0 on Turing tape]
            T#V     [reset count of steps]
            T4V     [initialize maximum position]
            T5V     [initialize minimum position]
[Calculate number of available tape positions; store in address field]
            A22N    [T order for exclusive end of tape]
            S21N    [T order for start of tape]
            L4F     [times 16, since each location holds 16 positions]
            T25N    [store for later use]
[Set up the loop in the main program that writes the initial pattern.
 The main program has a list of position-value pairs.
 This follows the list of rules, 2 rules per Turing machine state.]
      [9]   AA      [number of states]
            LD      [times 2, because 2 rules per state]
            A2F     [plus 1 for the count of states]
            A9@     [make A order to load number of position-value pairs]
            T14@    [plant order]
     [14]   AM      [load number of pairs (in address field)]
            LD      [times 2 for length of table]
            TF      [temp store in 0F]
            A14@    [load order that was planted above]
            A2F     [make order to load first position]
            U13M    [plant in main routine]
            AF      [make A order for exclusive end]
            T28M    [plant in main routine]
[Set up order to load rules]
            A26@
            A2F
            T18N
[Here with acc = 0. Jump to main routine.]
            EM
     [26]   AA
 
[============================= V parameter ===============================]
            E25K TV GK
      [0]   PFPF    [number of steps (35-bit, must be at even address)]
      [2]   PF      [current state of Turing machine]
      [3]   PF      [current tape position, stored in address field]
      [4]   PF      [maximum position on the tape so far]
      [5]   PF      [minimum position on the tape so far]
      [6]   PF      [rule for current state and symbol]
      [7]   PF      [working group of 16 cells (1 EDSAC location)]
      [8]   PF      [mask to select bit for current cell]
 
[============================= N parameter ===============================]
            E25K TN GK
[17-bit masks: 11111111111111110, 11111111111111101, ..., 10111111111111111]
      [0]   V2047F V2046D V2045D V2043D V2039D V2031D V2015D V1983D
            V1919D V1791D V1535D V1023D C2047D B2047D G2047D M2047D
     [16]   OF      [add to A order to make T order with same address]
     [17]   AN      [A order to load first mask in table]
     [18]   AF      [A order to load first rule]
     [19]   A&      [A order for start of tape]
     [20]   AA      [A order for end of tape]
     [21]   T&      [T order for start of tape]
     [22]   TA      [T order for exclusive end of tape]
     [23]   P2047F  [mask to pick out state from a Turing machine rule]
     [24]   P15F    [mask to extract bit number from position]
     [25]   PF      [number of tape positions available (calculated)]
     [26]   @F      [carriage return]
     [27]   &F      [line feed]
     [28]   K4096F  [null]
     [29]   K2048F  [set letters on teleprinter]
 
[============================= M parameter ===============================]
            E25K TM GK
[Once-only code jumps to here with acc = 0]
[Clear the tape; this overwrites the once-only code]
      [0]   A21N    [load T order for start of tape]
            E3@     [always jump (since T > 0)]
      [2]   A22N    [loop here after testing for end]
      [3]   T4@     [plant order to clear 1 location]
      [4]   TF      [execute order]
            A4@     [load order just executed]
            A2F     [inc address]
            S22N    [test for end]
            G2@     [if not end, loop back]
[Here with acc = 0]
[Set up the starting pattern, i.e write 1's at zero or more positions on the tape.]
[To save space, the orders marked (*) are set up by the once-only code.]
      [9]   A13@    [load A order for next relative addess]
            S28@    [compare with A order for exclusive end]
            E29@    [if all done, jump out with acc = 0]
            TF      [clear acc]
     [13]   AF      [(*) load relative address from table]
            G17@    [jump if < 0]
            A21N    [make T order, addr counted from low end of tape]
            E18@    [join commoon code (always jumps since T > 0)]
     [17]   A22N    [make T order, addr counted from high end of tape]
     [18]   T23@    [plant T order in code]
            A13@    [make order to load value from table]
            A2F
            T22@    [plant in code]
     [22]   AF      [load value from table]
     [23]   TF      [store in tape]
            A22@    [make A order for next address]
            A2F
            T13@    [plant in code]
            E9@     [always loop back]
     [28]   AF      [(*) A order for exclusive end of list]
     [29]
[Next step, i.e. set up new symbol, state and tape position.]
[Acc must be 0 here.]
[Get tape position and deduce corresponding EDSAC location and bit number.]
     [29]   H24N    [mask for bit number]
            C3V     [acc := bit number]
            UF      [save bit number in 0F address field]
            A17N    [make order to load from mask table]
            T44@    [plant order in code]
            A3V     [position]
            SF      [remove bit number part]
            R4F     [divide by 16 for relative address]
[If it's a non-negative address, add it to the start of the tape in EDSAC memory.]
[If it's a negative address, add it to the end of the tape.]
            G40@    [jump if negative address]
            A19N    [make A order to load from tape]
            G41@    [always jump to common code, since A < 0]
     [40]   A20N    [here if negative address]
     [41]   U46@    [store order to load current group of 16 bits]
            A16N    [convert to T order at same address]
            T69@    [store T order (a fair way down the code)]
     [44]   AF      [load mask]
            T8V
     [46]   AF      [load group]
            T7V
[Get rule for this state and symbol (where symbol = 0 or 1)]
            H8V
            C7V     [acc := bit group with current bit cleared]
            S7V     [acc := 0 if bit is 0, -1 if bit is 1]
            E54@
            TF      [clear acc]
            A2F     [to inc rule address if symbol is 1]
     [54]   A2V     [add state twice (because each state has 2 rules)]
            A2V
            A18N    [manufacture A order to load rule]
            T58@
     [58]   AF      [load rule]
            T6V     [to work space]
[Write new symbol (0 or 1) to tape. New symbol is in low bit of rule.]
            HN      [H register := 111...1110]
            C6V
            S6V     [result = 0 if new symbol is 0; -1 if it's 1]
            H8V     [H register = mask 1...101...1 for current bit]
            G67@    [jump to set the bit]
            C7V     [clear the bit]
            E69@    [always jump (because top bit in tape store is always 0)]
[Set bit, assuming acc = -1 here (reason why it works is a bit complicated)]
     [67]   C7V
            S8V
     [69]   TF      [manufactured order]
[Update position of tape head, i.e. inc by 1, dec by 1, or no change.]
[Move is in top 2 bits of rule, thus]
  [1x = move left, i.e. dec position (function letter can be L)]
  [00 = move right, i.e. inc position (function letter can be R)]
  [01 = stay, i.e. don't change position (function letter can be S)]
            A6V
            G83@    [left if top bit is 1]
     [72]   LD      [else test next bit]
            G95@    [skip move if next bit is 1]
     [74]   TF      [here to move right]
            A3V     [inc position]
            A2F
            U3V
[Here we update the maximum position if latest >= maximum.]
[This is unnecessary if latest = maximum, but code is simpler this way.]
            S4V     [test against maximum position]
            G95@    [skip if latest < maximum]
            A4V     [restore after test]
            T4V     [update maximum]
            E91@    [always jump, to check for overflow]
     [83]   TF      [here to move left]
            A3V     [dec position]
            S2F
     [86]   U3V
            S5V     [test against current minimum position]
            E95@    [jump if >= minimum]
            A5V     [restore acc after test]
            T5V     [update minimum]
[After updating maximum or minimum position, check that
   available memory hasn't been exceeded.]
     [91]   A4V     [maximum position]
            S5V     [subtract minimum position]
            S25N    [compare against number available]
            E107@   [jump out if overflow]
[The next order also serves as a constant]
     [95]   TF      [clear acc for next part]
[Increment the number of steps]
            A#V
            YFYF
            T#V
[Finally set the new state.]
    [100]   H23N    [mask for state bits in rule]
            C6V     [acc := new state]
            SA      [is it the last state?]
            E111@   [if yes, halt the Turing machine]
            AA      [restore acc after test]
            T2V     [update state]
            E29@    [loop back for next step]
[Overflow, i.e. non-negative tape positions (ascending in EDSAC memory)
 collide with negative tape positions (descending).]
    [107]   O29N    [set teleprinter to letters]
            O107@ ON  [print 'OV' to indicate overflow]
            E116@   [jump to exit]
[Print number of steps]
    [111]   TF A#V  [clear accc, load number of steps]
            TD      [number of steps to 0D for print subroutine
    [114]   A114 @GG  [call print subroutine]
    [116]   O26N O27N [print CR, LF]
            O28N    [print null to flush teleprinter buffer]
            ZF      [stop]
 
[============================= G parameter ===============================]
            E25K TG
  [Library subroutine P7. 35 locations, even address. WWG page 18.]
  [Prints non-negative integer, up to 10 digits, right-justified.]
            GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F
            T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
 
[========================== X parameter again ===============================]
            E25K TX GK
            EZ      [define entry point]
            PF      [enter with acc = 0]
[end]
 