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.




// Machine definitions
 
name = 1 : initState = 2 : endState = 3 : blank = 4 : countOnly = true
 
incrementer$ = "Simple incrementer,q0,qf,B"
incrementer$ = incrementer$ + ",q0,1,1,right,q0,q0,B,1,stay,qf"
 
threeStateBB$ = "Three-state busy beaver,a,halt,0"
data "a,0,1,right,b"
data "a,1,1,left,c"
data "b,0,1,left,a"
data "b,1,1,right,b"
data "c,0,1,left,b"
data "c,1,1,stay,halt"
data ""
 
do
    read a$
    if a$ = "" break
    threeStateBB$ = threeStateBB$ + "," + a$
loop
 
 
fiveStateBB$ = "Five-state busy beaver,A,H,0"
data "A,0,1,right,B"
data "A,1,1,left,C"
data "B,0,1,right,C"
data "B,1,1,right,B"
data "C,0,1,right,D"
data "C,1,0,left,E"
data "D,0,1,left,A"
data "D,1,1,left,D"
data "E,0,1,stay,H"
data "E,1,0,left,A"
data ""
 
do
    read a$
    if a$ = "" break
    fiveStateBB$ = fiveStateBB$ + "," + a$
loop
 
clear screen
 
// Display a representation of the tape and machine state on the screen
sub show(state$, headPos, tape$)
    local pos
 
    print " ", state$, "\t| ";
    for pos = 1 to len(tape$)
        if pos = headPos then print "[", mid$(tape$, pos, 1), "] "; else print " ", mid$(tape$, pos, 1), "  "; end if
    next
    print
end sub
 
sub string.rep$(s$, n)
    local i, r$
 
    for i = 1 to n
        r$ = r$ + s$
    next
 
    return r$
end sub
 
 
// Simulate a turing machine
sub UTM(mach$, tape$, countOnly)
    local state$, headPos, counter, machine$(1), n, m, rule
 
    m = len(tape$)
    n = token(mach$, machine$(), ",")
    state$ = machine$(initState)
    n = n - blank
    headPos = 1
 
    print "\n\n", machine$(name)
    print string.rep$("=", len(machine$(name))), "\n"
    if not countOnly print " State", "\t| Tape [head]\n----------------------"
 
    repeat
        if mid$(tape$, headPos, 1) = " " mid$(tape$, headPos, 1) = machine$(blank)
        if not countOnly show(state$, headPos, tape$)
        for rule = blank + 1 to n step 5
            if machine$(rule) = state$ and machine$(rule + 1) = mid$(tape$, headPos, 1) then
                mid$(tape$, headPos, 1) = machine$(rule + 2)
                if machine$(rule + 3) = "left" then
                    headPos = headPos - 1
                    if headPos < 1  then
                        headPos = 1
                        tape$ = " " + tape$ 
                    end if
                end if
                if machine$(rule + 3) = "right" then
                    headPos = headPos + 1
                    if headPos > m then
                        m = m + 1
                        tape$ = tape$ + " "
                    end if
                end if
                state$ = machine$(rule + 4)
                break
            end if
        next
        counter = counter + 1
    until(state$ = machine$(endState))
    if countOnly then print "Steps taken: ", counter else show(state$, headPos, tape$) end if
end sub
 
// Main procedure
UTM(incrementer$, "111")
UTM(threeStateBB$, " ")
UTM(fiveStateBB$, " ", countOnly)