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

UTM(incrementer, {"1", "1", "1"})
UTM(threeStateBB, {})
UTM(fiveStateBB, {}, countOnly:=1)