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.




with javascript_semantics
enum name, initState, endState, blank, rules
 
-- Machine definitions
constant incrementer = {
    /*name =*/ "Simple incrementer",
    /*initState =*/ "q0",
    /*endState =*/ "qf",
    /*blank =*/ "B",
    /*rules =*/ {
        {"q0", "1", "1", "right", "q0"},
        {"q0", "B", "1", "stay", "qf"}
    }
}
 
constant threeStateBB = {
    /*name =*/ "Three-state busy beaver",
    /*initState =*/ "a",
    /*endState =*/ "halt",
    /*blank =*/ "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"}
    }
}
 
constant fiveStateBB = {
    /*name =*/ "Five-state busy beaver",
    /*initState =*/ "A",
    /*endState =*/ "H",
    /*blank =*/ "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"}
    }
}
 
procedure show(string state, integer headpos, sequence tape)
    printf(1," %-6s | ",{state})
    for p=1 to length(tape) do
        printf(1,iff(p=headpos?"[%s]":" %s "),{tape[p]})
    end for
    printf(1,"\n")
end procedure
 
-- a universal turing machine
procedure UTM(sequence machine, sequence tape, integer countOnly=0)
    string state = machine[initState]
    integer headpos = 1, counter = 0
    printf(1,"\n\n%s\n%s\n",{machine[name],repeat('=',length(machine[name]))})
    if not countOnly then printf(1," State  | Tape [head]\n---------------------\n") end if
    while 1 do
        if headpos>length(tape) then
            tape = append(tape,machine[blank])
        elsif headpos<1 then
            tape = prepend(tape,machine[blank])
            headpos = 1
        end if
        if not countOnly then show(state, headpos, tape) end if
        for i=1 to length(machine[rules]) do
            sequence rule = machine[rules][i]
            if rule[1]=state and rule[2]=tape[headpos] then
                tape[headpos] = rule[3]
                if rule[4] == "left" then headpos -= 1 end if
                if rule[4] == "right" then headpos += 1 end if
                state = rule[5]
                exit
            end if
        end for
        counter += 1
        if state=machine[endState] then exit end if
    end while
    if countOnly then
        printf(1,"Steps taken: %d\n",{counter})
    else
        show(state, headpos, tape)
    end if
end procedure
 
atom t0 = time()
UTM(incrementer, {"1", "1", "1"})
UTM(threeStateBB, {})
if platform()!=JS then -- 1min 7s
    UTM(fiveStateBB, {}, countOnly:=1)
end if
?elapsed(time()-t0)
