Examples of Turing Machine Programs

Turing Machine Program

// Turing Machine for unary addition, expects 110111 -> 11111

CONFIG:
    START: start
    ACCEPT: success
    REJECT: fail


MAIN:
    start, 1 -> 1, R, start
    start, 0 -> 1, R, q1

    q1, 1 -> 1, R, q1
    q1, _ -> _, L, q2
    q2, 1 -> _, S, success

State Machine Visualization

Turing Machine Program

// TM to recognise strings with equal a's and b's
// Strictly follows the order of a then b, always looking for 'a' first
// Then moving to start to find corresponding b

CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, X -> X, R, q0
    q0, b -> b, R, q0
    q0, a -> X, L, q1
    q0, _ -> _, S, success // If you see blank on q0, then the complete string is covered

    q1, a -> a, L, q1
    q1, b -> b, L, q1
    q1, X -> X, L, q1
    q1, _ -> _, R, q2

    q2, X -> X, R, q2
    q2, a -> a, R, q2
    q2, b -> X, L, q3


    q3, a -> a, L, q3
    q3, b -> b, L, q3
    q3, X -> X, L, q3
    q3, _ -> _, R, q0

State Machine Visualization

Turing Machine Program

CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, 0 -> 1, R, q0
    q0, 1 -> 0, R, q0
    q0, _ -> _, S, success

State Machine Visualization

Turing Machine Program

CONFIG:
    START: start
    ACCEPT: done
    REJECT: fail

MACROS:
    DEF move_right_end:
        q, 0 -> 0, R, q
        q, 1 -> 1, R, q
        q, _ -> _, L, RETURN
    DEF move_left_end:
        q, 0 -> 0, L, q
        q, 1 -> 1, L, q
        q, _ -> _, R, RETURN

MAIN:
    start, 0 -> _, R, CALL move_right_end -> q1
    start, 1 -> _, R, CALL move_right_end -> q2
    start, _ -> _, S, done
    
    q1, 0 -> _, L, CALL move_left_end -> start
    q1, 1 -> 1, S, fail
    q1, _ -> _, S, done

    q2, 1 -> _, L, CALL move_left_end -> start
    q2, 0 -> 0, S, fail
    q2, _ -> _, S, done

State Machine Visualization

Turing Machine Program

// Takes a string, 1011 -> 1101

CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, 1 -> 1, R, q0
    q0, 0 -> 0, R, q0
    q0, _ -> _, L, q1

    q1, 1 -> X, R, q2
    q1, 0 -> X, R, q3
    q1, X -> X, L, q1
    q1, _ -> _, R, q5
  

    q2, X -> X, R, q2
    q2, 0 -> 0, R, q2
    q2, 1 -> 1, R, q2
    q2, _ -> 1, L, q4

    q3, X -> X, R, q3
    q3, 0 -> 0, R, q3
    q3, 1 -> 1, R, q3
    q3, _ -> 0, L, q4

    q4, X -> X, L, q1
    q4, 1 -> 1, L, q4
    q4, 0 -> 0, L, q4

    q5, X -> _, R, q5
    q5, 1 -> 1, S, success
    q5, 0 -> 0, S, success

State Machine Visualization

Turing Machine Program

// Unary subtraction (absolute value), expects 111011 -> 1

CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, 1 -> _, R, q1
    q0, 0 -> _, S, success
    
    q1, 1 -> 1, R, q1
    q1, 0 -> 0, R, q1
    q1, _ -> _, L, q2

    q2, 1 -> _, L, q3
    q2, 0 -> 1, S, success

    q3, 1 -> 1, L, q3
    q3, 0 -> 0, L, q3
    q3, _ -> _, R, q0

State Machine Visualization

Turing Machine Program

CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, 0 -> 0, R, q0
    q0, 1 -> 1, R, q0
    q0, _ -> _, L, q1
    

    q1, 0 -> 0, L, q1
    q1, 1 -> 1, L, q2

    q2, 0 -> 1, L, q2
    q2, 1 -> 0, L, q2
    q2, _ -> _, S, success

State Machine Visualization

Turing Machine Program

// E2pects input as 1101110, 223 = 6 , 1101110111111, a*b
CONFIG:
    START: q0
    ACCEPT: success
    REJECT: fail

MAIN:
    q0, 0 -> 0, S, success
    q0, 1 -> _, R, q1

    q1, 1 -> 1, R, q1
    q1, 0 -> 0, R, q2

    q2, 1 -> X, R, q3
    q2, 0 -> 0, L, q6

    q3, 1 -> 1, R, q3
    q3, 0 -> 0, R, q4

    q4, 1 -> 1, R, q4
    q4, _ -> 1, L, q5

    q5, 0 -> 0, L, q5
    q5, 1 -> 1, L, q5
    q5, X -> X, R, q2

    q6, X -> 1, L, q6
    q6, 0 -> 0, L, q7

    q7, 1 -> 1, L, q7
    q7, _ -> _, R, q0

State Machine Visualization