' Turing Machine — simulates a simple Turing machine
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL tape(10000) AS LONG
    LOCAL headPos AS LONG
    LOCAL state AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL steps AS LONG
    LOCAL maxSteps AS LONG
    LOCAL tapeLen AS LONG
    LOCAL symbol AS LONG
    LOCAL newSymbol AS LONG
    LOCAL moveDir AS LONG
    LOCAL newState AS LONG
    LOCAL done AS LONG
    LOCAL tapeStr AS STRING
    LOCAL lineStr AS STRING
    tapeLen = 100
    maxSteps = 1000
    PRINT "============================================"
    PRINT "        TURING MACHINE SIMULATOR"
    PRINT "============================================"
    PRINT ""
    PRINT "Binary increment (add 1 to binary number)"
    PRINT ""
    FOR i = 0 TO tapeLen - 1
        tape(i) = 0
    NEXT i
    headPos = 20
    tape(headPos) = 1
    tape(headPos + 1) = 0
    tape(headPos + 2) = 1
    tape(headPos + 3) = 1
    PRINT "Initial tape (binary 1011 = 11):"
    tapeStr = ""
    FOR i = 0 TO tapeLen - 1
        IF tape(i) = 0 THEN
            tapeStr = tapeStr + "0"
        ELSE
            tapeStr = tapeStr + "1"
        END IF
    NEXT i
    PRINT " " + tapeStr
    PRINT " Head at position " + STR$(headPos)
    PRINT ""
    state = 0
    steps = 0
    done = 0
    DO WHILE done = 0 AND steps < maxSteps
        IF headPos < 0 THEN
            headPos = 0
        END IF
        IF headPos >= tapeLen THEN
            headPos = tapeLen - 1
        END IF
        symbol = tape(headPos)
        IF state = 0 THEN
            IF symbol = 0 THEN
                tape(headPos) = 1
                headPos = headPos + 1
                state = 2
            ELSE
                tape(headPos) = 0
                headPos = headPos + 1
                state = 1
            END IF
        ELSE
            IF state = 1 THEN
                IF symbol = 0 THEN
                    tape(headPos) = 1
                    headPos = headPos + 1
                    state = 2
                ELSE
                    tape(headPos) = 0
                    headPos = headPos + 1
                    state = 1
                END IF
            ELSE
                IF state = 2 THEN
                    done = 1
                END IF
            END IF
        END IF
        steps = steps + 1
    LOOP
    PRINT "Result after " + STR$(steps) + " steps:"
    tapeStr = ""
    FOR i = 0 TO tapeLen - 1
        IF tape(i) = 0 THEN
            tapeStr = tapeStr + "0"
        ELSE
            tapeStr = tapeStr + "1"
        END IF
    NEXT i
    PRINT " " + tapeStr
    PRINT ""
    PRINT "============================================"
    PRINT "     BUSY BEAVER (2-state, 2-symbol)"
    PRINT "============================================"
    PRINT ""
    FOR i = 0 TO tapeLen - 1
        tape(i) = 0
    NEXT i
    headPos = 50
    state = 0
    steps = 0
    done = 0
    maxSteps = 1000
    DO WHILE done = 0 AND steps < maxSteps
        IF headPos < 0 THEN
            headPos = 0
        END IF
        IF headPos >= tapeLen THEN
            headPos = tapeLen - 1
        END IF
        symbol = tape(headPos)
        IF state = 0 THEN
            IF symbol = 0 THEN
                tape(headPos) = 1
                headPos = headPos + 1
                state = 1
            ELSE
                tape(headPos) = 1
                headPos = headPos - 1
                state = 1
            END IF
        ELSE
            IF state = 1 THEN
                IF symbol = 0 THEN
                    tape(headPos) = 1
                    headPos = headPos - 1
                    state = 0
                ELSE
                    tape(headPos) = 1
                    headPos = headPos + 1
                    done = 1
                END IF
            END IF
        END IF
        steps = steps + 1
    LOOP
    PRINT "Busy Beaver (2-state, 2-symbol):"
    PRINT " Steps: " + STR$(steps)
    PRINT ""
    PRINT "============================================"
    PRINT "     UNARY ADDITION (1+1)"
    PRINT "============================================"
    PRINT ""
    FOR i = 0 TO 99
        tape(i) = 0
    NEXT i
    tape(20) = 1
    tape(21) = 1
    tape(22) = 1
    tape(23) = 0
    tape(24) = 1
    tape(25) = 1
    tape(26) = 1
    headPos = 20
    state = 0
    steps = 0
    done = 0
    maxSteps = 500
    DO WHILE done = 0 AND steps < maxSteps
        IF headPos < 0 THEN
            headPos = 0
        END IF
        IF headPos >= 100 THEN
            headPos = 99
        END IF
        symbol = tape(headPos)
        IF state = 0 THEN
            IF symbol = 1 THEN
                headPos = headPos + 1
            ELSE
                tape(headPos) = 1
                headPos = headPos - 1
                state = 1
            END IF
        ELSE
            IF state = 1 THEN
                IF symbol = 1 THEN
                    headPos = headPos - 1
                ELSE
                    tape(headPos) = 0
                    done = 1
                END IF
            END IF
        END IF
        steps = steps + 1
    LOOP
    PRINT "Unary addition (3 + 3):"
    tapeStr = ""
    ones = 0
    FOR i = 0 TO 99
        IF tape(i) = 1 THEN
            ones = ones + 1
        END IF
    NEXT i
    PRINT " Steps: " + STR$(steps) + "  Ones: " + STR$(ones)
    PRINT ""
    PRINT "============================================"
    PRINT "     COPY ROUTINE (simple duplication)"
    PRINT "============================================"
    PRINT ""
    FOR i = 0 TO 99
        tape(i) = 0
    NEXT i
    tape(10) = 1
    tape(11) = 0
    tape(12) = 1
    headPos = 10
    state = 0
    steps = 0
    done = 0
    maxSteps = 2000
    LOCAL copyBuffer(100) AS LONG
    LOCAL bufCount AS LONG
    bufCount = 0
    DO WHILE headPos < 100 AND steps < maxSteps
        IF tape(headPos) = 1 THEN
            copyBuffer(bufCount) = 1
            bufCount = bufCount + 1
        END IF
        IF tape(headPos) = 0 AND bufCount > 0 THEN
            EXIT DO
        END IF
        headPos = headPos + 1
        steps = steps + 1
    LOOP
    headPos = 30
    FOR i = 0 TO bufCount - 1
        tape(headPos) = copyBuffer(i)
        headPos = headPos + 1
    NEXT i
    tapeStr = ""
    FOR i = 0 TO 49
        IF tape(i) = 0 THEN
            tapeStr = tapeStr + "0"
        ELSE
            tapeStr = tapeStr + "1"
        END IF
    NEXT i
    PRINT "Copy result (original + copy):"
    PRINT " " + tapeStr
    PRINT ""
    PRINT "============================================"
    PRINT "     SUBROUTINE CALL (state stacking)"
    PRINT "============================================"
    PRINT ""
    FOR i = 0 TO 99
        tape(i) = 0
    NEXT i
    tape(15) = 1
    tape(16) = 1
    tape(17) = 1
    headPos = 15
    state = 0
    steps = 0
    done = 0
    maxSteps = 500
    DO WHILE done = 0 AND steps < maxSteps
        IF headPos < 0 THEN
            headPos = 0
        END IF
        IF headPos >= 100 THEN
            headPos = 99
        END IF
        symbol = tape(headPos)
        IF state = 0 THEN
            IF symbol = 1 THEN
                tape(headPos) = 0
                headPos = headPos + 1
            ELSE
                headPos = headPos - 1
                state = 1
            END IF
        ELSE
            IF state = 1 THEN
                done = 1
            END IF
        END IF
        steps = steps + 1
    LOOP
    PRINT "Erase pattern: " + STR$(steps) + " steps"
    PRINT ""
    PRINT "Turing machine simulation complete"
    FUNCTION = 0
END FUNCTION
