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.




record TM(start,final,delta,tape,blank)
record delta(old_state, input_symbol, new_state, output_symbol, direction)
 
global start_tape
global show_count, full_display, trace_list  # trace flags
 
procedure main(args)
    init(args)
    runTuringMachine(get_tm())
end
 
procedure init(args)
    trace_list := ":"
    while arg := get(args) do {
        if arg == "-f" then full_display := "yes"
        else if match("-t",arg) then trace_list ||:= arg[3:0]||":"
        else show_count := integer(arg)
        }
end
 
procedure get_tm()
    D := table()
 
    writes("What is the start state? ")
    start := !&input
    writes("What are the final states (colon separated)? ")
    finals := !&input
    (finals||":") ? every insert(fStates := set(), 1(tab(upto(':')),move(1)))
    writes("What is the tape blank symbol?")
    blank := !&input
 
    write("Enter the delta mappings, using the following format:")
    write("\tenter delta(curState,tapeSymbol) = (newState,newSymbol,direct) as")
    write("\t   curState:tapeSymbol:newState:newSymbol:direct");
    write("\t\twhere direct is left, right, stay, or halt")
    write("End with a blank line.")
    write("")
    every line := !&input do {
        if *line = 0 then break
        line ?
             if (os := tab(upto(':')), move(1), ic := tab(upto(':')), move(1),
                 ns := tab(upto(':')), move(1), oc := tab(upto(':')), move(1),
                 d  := map(tab(0))) then D[os||":"||ic] := delta(os,ic,ns,oc,d)
             else write(line, " is in bad form, correct it")
        }
    if /start_tape then {
        write("Enter the input tape")
        start_tape := !&input
        }
    return TM(start,fStates,D,start_tape,blank)
end
 
procedure runTuringMachine(tm)
    trans := tm.delta
    rightside := tm.tape
    if /rightside | (*rightside = 0) then rightside := tm.blank
    leftside := ""
 
    cur_state := tm.start
    write("Machine starts in ",cur_state," with tape:")
    show_tape(tm,leftside,rightside)
    while mapping := \trans[cur_state||":"||rightside[1]] do {
        rightside[1] := mapping.output_symbol
        case mapping.direction of {
            "left" : {
                 if *leftside = 0 then leftside := tm.blank
                 rightside := leftside[-1] || rightside
                 leftside[-1] := ""
                 }
            "right" : {
                 leftside ||:= rightside[1]
                 rightside[1] := ""
                 if *rightside = 0 then rightside := tm.blank
                 }
            "halt" : break
            }
        cur_state := mapping.new_state
        if member(tm.final,cur_state) then break
        trace(tm,cur_state,leftside,rightside)
        }
    write()
    write("Machine halts in ",cur_state," with tape:")
    show_tape(tm,leftside,rightside)
end
 
procedure trace(tm,cs,ls,rs)
    static count, last_state
    initial {
       count := 0
       last_state := ""
       }
 
    count +:= 1
    if \show_count & (count % show_count = 0) then show_tape(tm,ls,rs)
    if find(":"||cs||":",trace_list) & (last_state ~== cs) then { 
        writes("\tnow in state: ",cs," ")
        if \full_display then show_delta(tm.delta[cs||":"||rs[1]])
        else write()
        }
    last_state := cs
    return
end
 
procedure show_delta(m)
    if /m then write("NO MOVE!")
    else {
        writes("\tnext move is ")
        writes("delta(",m.old_state,",",m.input_symbol,") ::= ")
        write("(",m.new_state,",",m.output_symbol,",",m.direction,")")
        }
end
 
procedure show_tape(tm,l,r)
    l := reverse(trim(reverse(l),tm.blank))
    r := trim(r,tm.blank)
    write(l,r)
    write(repl(" ",*l),"^")
end