turing-machine.ts

const enum Direction {
  L = 0,
  R = 1,
}
const enum Alphabet {
  A = 0,
  B = 1,
}
type StateOutput = [
  Alphabet, // write
  Direction, // move
  number // next
];
type State = [StateOutput, StateOutput];
type Program = Array<State>;
type Tape = Array<Alphabet>;

interface Debugger {
  step?(tape: Tape, position: number, state: State): any;
}

function run(program: Program, tape: Tape = [], debug?: Debugger) {
  let position = 0;
  let state = program[0];
  while (state && !(debug?.step && debug.step(tape, position, state))) {
    const [write, move, next] = state[tape[position] || Alphabet.A];
    tape[position] = write;
    position += 2 * move - 1;
    if (position == -1) {
      tape.unshift(Alphabet.A);
      position = 0;
    }
    state = program[next!];
  }
  return { tape, position };
}

console.log(
  run([
    [
      [Alphabet.B, Direction.R, 1],
      [Alphabet.B, Direction.L, 2],
    ],
    [
      [Alphabet.B, Direction.L, 0],
      [Alphabet.B, Direction.R, 1],
    ],
    [
      [Alphabet.B, Direction.L, 1],
      [Alphabet.B, Direction.R, -1],
    ],
  ])
);