Implementing copy with two instructions: D (duplicate), T (translate)

turing.ts

////////////////////////////////////////////////////////////////
// Types
////////////////////////////////////////////////////////////////

// # Instruction Set # Program # Registers # Memory #

// NOTE: Things would be way easier if we knew:
// - Which sector we're currently in: Program, Registers, Memory
// - Which direction we previously moved
//
// From what I can tell the only to get this information is to
// encode it into the set of states. Using a tuple or a record
// is cheating, so instead we will need to state the 
// Cartesian Product of State x Sector x Direction, which
// unfortunately is cumbersome to write. Ideally we would write
// some compiler to handle this for us.

enum State {
    Init = "INIT",
    ReadInstruction = "READ",
    MoveToEnd = "M2E",
    MoveToBeg = "M2B",
    MoveToDup1 = "M2D1",
    MoveToDup2 = "M2D2",
    Discard = "DSC",
    Flip = "FLP",
    Flip0 = "FLP0",
    Flip1 = "FLP1",
    Accept = "ACPT",
    Reject = "RJCT",
    Duplicate = "DUP",
    Duplicate0Skip = "DUP0S",
    Duplicate1Skip = "DUP1S",
    Duplicate0Write = "DUP0W",
    Duplicate1Write = "DUP1W",
    Translate = "TRS",
}
type Head = { i: number; state: State; };

enum Alphabet {
    Zero = "0",
    One = "1",
    ZeroTomb = "x",
    OneTomb = "y",
    Hash = "#",
    Discarded = "X",
    SectorSep = "|",
    NewMemory = "&",
    EOL = "$",
    Flip = "F",
    Alternate = "A",
    Duplicate = "D",
    Translate = "T",
};

enum Direction {
    Right = "R",
    Left = "L",
    Stay = "_",
};

type Tape = Alphabet[];
type Program = {
    head: Head;
    tape: Tape;
};

type Transition = (program: Program) => [Alphabet | null, Direction, State];

////////////////////////////////////////////////////////////////
// Library
////////////////////////////////////////////////////////////////

function matches(state: State, v: Alphabet | null, program: Program): boolean {
    return program.head.state === state && (v === null ? true : program.tape[program.head.i] === v);
}

function compile(table: string): Transition {
    const states: {[x: string]: State} = {
        "INIT": State.Init,
        "READ": State.ReadInstruction,
        "M2E": State.MoveToEnd,
        "M2B": State.MoveToBeg,
        "M2D1": State.MoveToDup1,
        "M2D2": State.MoveToDup2,
        "DSC": State.Discard,
        "FLP": State.Flip,
        "FLP0": State.Flip0,
        "FLP1": State.Flip1,
        "ACPT": State.Accept,
        "RJCT": State.Reject,
        "DUP": State.Duplicate,
        "DUP0S": State.Duplicate0Skip,
        "DUP1S": State.Duplicate1Skip,
        "DUP0W": State.Duplicate0Write,
        "DUP1W": State.Duplicate1Write,
        "TRS": State.Translate,
    };
    const alphabet: {[x: string]: Alphabet} = {
        "$": Alphabet.EOL,
        "F": Alphabet.Flip,
        "A": Alphabet.Alternate,
        "D": Alphabet.Duplicate,
        "T": Alphabet.Translate,
        "X": Alphabet.Discarded,
        "#": Alphabet.Hash,
        "|": Alphabet.SectorSep,
        "&": Alphabet.NewMemory,
        "0": Alphabet.Zero,
        "1": Alphabet.One,
        "x": Alphabet.ZeroTomb,
        "y": Alphabet.OneTomb,
        "_": null,
    };
    const directions: {[x: string]: Direction} = {
        "R": Direction.Right,
        "L": Direction.Left,
        "_": Direction.Stay,
    };
    const rules: string[] = table.trim().split("\n").filter((x) => x.trim() !== "");
    const ruleIdx: {[x: string]: [State, Alphabet | null, Alphabet | null, Direction, State][]} = {};
    for (const rule of rules) {
        const [s0, read, write, dir, s1] = rule.trim().split(/\s+/);
        const [a, b, c, d, e] = [states[s0], alphabet[read], alphabet[write], directions[dir], states[s1]];
        if (typeof a === "undefined") throw new Error(`Failed to decode s0: ${s0}`);
        if (typeof b === "undefined") throw new Error(`Failed to decode read: ${read}`);
        if (typeof c === "undefined") throw new Error(`Failed to decode write: ${write}`);
        if (typeof d === "undefined") throw new Error(`Failed to decode direction: ${dir}`);
        if (typeof e === "undefined") throw new Error(`Failed to decode s1: ${s1}`);
        if (!ruleIdx[a]) {
            ruleIdx[a] = [];
        }
        ruleIdx[a].push([a, b, c, d, e]);
    }
    return (program) => {
        const xs = ruleIdx[program.head.state] ?? [];
        for (const rule of xs) {
            const [s0, read, write, move, s1] = rule;
            if (matches(s0, read, program)) {
                return [write, move, s1];
            }
        }        
        throw new Error(`Unsupported pattern: ${program.head.state} ${program.tape[program.head.i]}`);
    };
}

const transition = compile(`
    INIT _ _ R READ

    READ $ _ R M2E
    READ F _ R FLP
    READ | _ _ ACPT
    READ A _ R FLP0
    READ D _ R DUP
    READ T _ R TRS

    M2E  # _ L M2B
    M2E  _ _ R M2E

    M2B  $ _ L M2B
    M2B  # _ R DSC
    M2B  _ _ L M2B

    DSC  X _ R DSC
    DSC  _ X R READ

    FLP  0 1 R FLP
    FLP  1 0 R FLP
    FLP  # _ L M2B
    FLP  _ _ R FLP

    FLP0 | _ R FLP0
    FLP0 0 1 R FLP1
    FLP0 1 _ R FLP1
    FLP0 # _ L M2B

    FLP1 1 0 R FLP0
    FLP1 0 _ R FLP0

    DUP | _ R DUP
    DUP # _ L M2B
    DUP 0 x R DUP0S
    DUP 1 y R DUP1S
    DUP _ _ R DUP

    DUP0S & _ R DUP0W
    DUP0S _ _ R DUP0S

    DUP0W y _ R DUP0W
    DUP0W 0 x L M2D2
    DUP0W x _ R DUP0W

    DUP1S & _ R DUP1W
    DUP1S _ _ R DUP1S

    DUP1W x _ R DUP1W
    DUP1W y _ R DUP1W
    DUP1W 0 y L M2D2

    M2D2 & _ L M2D1
    M2D2 x _ L M2D2
    M2D2 y _ L M2D2

    M2D1 0 _ L M2D1
    M2D1 1 _ L M2D1
    M2D1 x _ R DUP
    M2D1 y _ R DUP

    TRS x 0 R TRS
    TRS y 1 R TRS
    TRS # _ L M2B
    TRS _ _ R TRS
`);

////////////////////////////////////////////////////////////////
// Main
////////////////////////////////////////////////////////////////

function decode(tape: string): Tape {
    return tape.split(" ").map((x) => {
        const y = {
            "#": Alphabet.Hash,
            "0": Alphabet.Zero,
            "1": Alphabet.One,
            "$": Alphabet.EOL,
            "|": Alphabet.SectorSep,
            "F": Alphabet.Flip,
            "A": Alphabet.Alternate,
            "D": Alphabet.Duplicate,
            "T": Alphabet.Translate,
            "&": Alphabet.NewMemory,
        }[x];
        if (typeof y === "undefined") {
            throw new Error(`Unsupported character: ${x}`);
        }
        return y;
    });
}

let program: Program = {
    head: { i: 0, state: State.Init },
    // Schema: # PROGRAM # RAM #
    tape: decode("# D T | 1 0 1 0 & 0 0 0 0 #"),
};

let s: number = 0;
while (![State.Accept, State.Reject].includes(program.head.state)) {
    console.log(`[ ${program.tape.join(" | ")} ] ${program.head.state}`);
    console.log(" ".repeat(program.head.i * 4) + "  ^ ");
    if (s > 160) {
        console.log("Exhausted");
        break;
    }
    const [w, direction, state] = transition(program);
    if (w !== null) {
        program.tape[program.head.i] = w;
    }
    program.head.state = state;
    switch (direction) {
        case Direction.Left: {
            program.head.i -= 1;
            break;
        }
        case Direction.Right: {
            program.head.i += 1;
            break;
        }
    }
    s += 1;
}
if (program.head.state === State.Accept) {
    console.log("Success!");
} else {
    console.log("Failure.");
}