// Transition function

f("q0", " ") => ["qa", " ", "R"];
f("qa", " ") => ["qA", " ", "L"];
f("qa", "a") => ["qb", "x", "R"];
f("qa", "b") => ["qR", "b", "L"];
f("qa", "c") => ["qR", "c", "L"];
f("qa", "x") => ["qa", "x", "R"];
f("qb", " ") => ["qR", " ", "L"];
f("qb", "a") => ["qb", "a", "R"];
f("qb", "b") => ["qc", "x", "R"];
f("qb", "c") => ["qR", "c", "L"];
f("qb", "x") => ["qb", "x", "R"];
f("qc", " ") => ["qR", " ", "L"];
f("qc", "a") => ["qR", "c", "L"];
f("qc", "b") => ["qc", "b", "R"];
f("qc", "c") => ["qL", "x", "L"];
f("qc", "x") => ["qc", "x", "R"];
f("qA", " ") => ["ha", " ", "S"];
f("qA", "x") => ["qA", "x", "L"];
f("qL", " ") => ["qa", " ", "R"];
f("qL", "a") => ["qL", "a", "L"];
f("qL", "b") => ["qL", "b", "L"];
f("qL", "c") => ["qL", "c", "L"];
f("qL", "x") => ["qL", "x", "L"];
f("qR", " ") => ["hr", " ", "S"];
f("qR", "a") => ["qR", "a", "L"];
f("qR", "b") => ["qR", "b", "L"];
f("qR", "c") => ["qR", "c", "L"];
f("qR", "x") => ["qR", "x", "L"];


// TM single-step function

step([L, Q, [X | M]]) => step1(L, f(Q, X), [X | M]);

step([L, Q, []])      => step([L, Q, [" "]]);   // Add more tape on right


// This auxiliary step function discriminates based on the "move" symbol.
// The left tape is reversed for convenient access to its rightmost symbol.

step1(L,       [P, Y, "R"], [_ | M]) => [[Y | L], P, M];            // Right

step1(L,       [P, Y, "S"], [_ | M]) => [L,       P, [Y | M]];      // None

step1([Z | L], [P, Y, "L"], [_ | M]) => [L,       P, [Z, Y | M]];   // Left

step1([],      [P, Y, "L"], [_ | M]) => [L,       P, [" ", Y | M]]; // Mo' tape


// TM run Function

run([L, "ha", M]) => [[L, "ha", M]];            // Halt and accept

run([L, "hr", M]) => [[L, "hr", M]];            // Halt and reject

run(State) => [State | run(step(State))];       // Keep running


// Debugging: run(N, State) runs for at most N steps from State.

run(0, State) => State;

run(_, [L, "ha", M]) => [[L, "ha", M]];

run(_, [L, "hr", M]) => [[L, "hr", M]];

run(N, State) => [State | run(N-1, step(State))];


// Format a sequence of states so it looks nicer

format([]) => ["\n"];
format([State | States]) => [format1(State) | format(States)];

format1([L, Q, R]) => [reverse(L), Q, R, "\n"];


// Create the initial state from an initial tape

initial(Tape) = [[], "q0", Tape];


// Test a given initial tape

test(Tape) = ["\n" | format(run(initial(Tape)))];


// A list of test tapes that should be accepted

good = [[" "],
        [" ", "a", "b", "c"],
        [" ", "a", "a", "b", "b", "c", "c"],
        [" ", "a", "a", "a", "b", "b", "b", "c", "c", "c"]
       ];

// A list of test tapes that should not be accepted

bad =  [
        [" ", "a"],
        [" ", "b"],
        [" ", "c"],
        [" ", "a", "a"],
        [" ", "a", "b"],
        [" ", "a", "c"],
        [" ", "a", "c"],
        [" ", "a", "a", "b", "c", "c"],
        [" ", "a", "b", "b", "c", "c"],
        [" ", "a", "a", "b", "b", "c"],
        [" ", "a", "a", "a", "b", "b", "b", "c", "c"],
       ];

test() = append(map(test#1, good), map(test#1, bad));