// 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)