Baby's first Turing Machine emulator

turing.ts

// Turing Machine emulator implemented in TypeScript.
// For awhile I've known what a Turing Machine represented in computing,
// by regurgitating to someone that "it can compute anything". I could
// even explain how there was a tape, a read/writer, symbols, and on
// better days I would even name-drop "cellular automata", but if actually
// attempting to emulate (easy) and *program* (difficult) a Turing Machine
// was a totally new can of worms for me... a bit of a cold shower.
//
// NOTE: I cheated by incrementing the numbers (only god will judge me)
//
// I'm ideally building-up to implementing the following:
//   - Counter with 1bit state, 1bit data (if possible)
//   - Stack-based MISC (less interested in the data widths for this)

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

enum Mode {
    Increment = "INC",
    MoveRight = "MR",
    MoveLeft = "ML",
    Discard = "DSC",
    DiscardCheck = "DS?";
    DiscardOk = "DOK";
    Halt = "HLT",
}
type State = { i: number; mode: Mode; };
enum Datum {
    Zero = "0",
    One = "1",
    Two = "2",
    Three = "3",
    Four = "4",
    Five = "5",
    Six = "6",
    Seven = "7",
    Eight = "8",
    Nine = "9",
    BOL = "^",
    EOL = "$",
};
type Tape = Datum[];
type Program = {
    state: State;
    tape: Tape;
};

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

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

function write(v: Datum, program: Program): void {
    program.tape[program.state.i] = v;
}

function step(program: Program): void {
    // Move Right
    if (matches(Mode.MoveRight, Datum.EOL, program)) {
        program.state.mode = Mode.Increment;
        program.state.i -= 1;
    }
    else if (matches(Mode.MoveRight, null, program)) {
        program.state.i += 1;
    }
    
    // Move Left
    else if (matches(Mode.MoveLeft, Datum.BOL, program)) {
        program.state.mode = Mode.Discard;
        program.state.i += 1;
    }
    else if (matches(Mode.MoveLeft, null, program)) {
        program.state.i -= 1;
    }

    // Discard
    else if (matches(Mode.Discard, null, program)) {
        program.state.mode = Mode.DiscardCheck;
        program.state.i += 1;
    }
    else if (matches(Mode.DiscardCheck, Datum.EOL, program)) {
        program.state.mode = Mode.Halt;
        program.state.i -= 1;
    }
    else if (matches(Mode.DiscardCheck, null, program)) {
        program.state.mode = Mode.DiscardOk;
        program.state.i -= 1;
    }
    else if (matches(Mode.DiscardOk, null, program)) {
        write(Datum.BOL, program);
        program.state.mode = Mode.MoveRight;
    }

    
    // Increment
    else if (matches(Mode.Increment, Datum.Zero, program)) {
        write(Datum.One, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.One, program)) {
        write(Datum.Two, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Two, program)) {
        write(Datum.Three, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Three, program)) {
        write(Datum.Four, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Four, program)) {
        write(Datum.Five, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Five, program)) {
        write(Datum.Six, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Six, program)) {
        write(Datum.Seven, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Seven, program)) {
        write(Datum.Eight, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Eight, program)) {
        write(Datum.Nine, program);
        program.state.mode = Mode.MoveLeft;
    }
    else if (matches(Mode.Increment, Datum.Nine, program)) {
        write(Datum.Zero, program);
        program.state.mode = Mode.MoveLeft;
    }
    
    // Oops...
    else {
        throw new Error(`Unsupported state transition: ${program.state.mode} ${program.tape[program.state.i]}`);
    }
}

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


let program: Program = {
    state: { i: 0, mode: Mode.MoveRight },
    tape: [
        Datum.BOL, Datum.Zero, Datum.Zero, Datum.Zero, Datum.EOL,
    ],
}

let s: number = 0;
while (program.state.mode !== Mode.Halt) {
    console.log(`Stepping: ${program.state.mode} ${program.tape[program.state.i]}`);
    console.log(`[ ${program.tape.join(" | ")} ]`);
    if (s > 40) {
        console.log("Exhausted")
        break;
    }
    step(program);
    s += 1;
}
console.log("Done.")