Compiler that translates a program for a Turing Machine with arbitrary marks, into a program for a Turing Machine that only uses ones and zeroes

binary-encoded.js

// binary encode a possibly unflattened instruction set with
// marks beyond 0 and 1
function binaryEncoded ({ description: descriptionWithMarks, tape: tapeWithMarks = [], LEFT, RIGHT, HALT, Write, Move }) {
  const recognizeStates = new Set();

  const marks = new PseudoSet();

  for (const [currentState, currentMark, nextState, ...instructions] of descriptionWithMarks) {
    recognizeStates.add(currentState);

    for (const instruction of instructions) {
      if (instruction instanceof Write) {
        marks.add(instruction.mark);
      }
    }
  }

  for (const cell of tapeWithMarks) {
    marks.add(cell);
  }

  const markToNumber = new PseudoMap();
  const numberToMark = new PseudoMap();

  const numbers = marks
    .filter(m => typeof m === 'number')
    .sort((a,b) => a < b ? -1 : (a === b ? 0 : 1));

  for (const number of numbers) {
    markToNumber.set(number, number);
    numberToMark.set(number, number);
  }

  let lastNumber = 0;

  const strings = marks.filter(m => typeof m === 'string');

  for (const string of strings) {
    while (numbers.includes(lastNumber)) ++lastNumber;
    markToNumber.set(string, lastNumber);
    numberToMark.set(lastNumber, string);
    ++lastNumber;
  }

  const others = marks.filter(m => typeof m !== 'string' && typeof m !== 'number');

  for (const other of others) {
    while (numbers.includes(lastNumber)) ++lastNumber;
    markToNumber.set(other, lastNumber);
    numberToMark.set(lastNumber, other);
    ++lastNumber;
  }

  // for (const key of markToNumber.keys()) {
  //   console.log(key.toString(), markToNumber.get(key));
  // }

  const bits = Math.max(1, Math.ceil(Math.log2(markToNumber.size)));

  // console.log(`bits: ${bits}`)

  const toReverseBinary = n =>
    n.toString(2).split('').map(b => '01'.indexOf(b)).reverse();

  const fromReverseBinary = array =>
    array.map((bit, i) => bit * Math.pow(2, i)).reduce((_, __) => _+__);

  const toPaddedReverseBinary = (n, length = bits) => {
    const rb = toReverseBinary(n);
    const padN = length - rb.length;

    for (let i = 0; i < padN; ++i) {
      rb.push(0);
    }

    return rb;
  };

  // for (const { key, value } of markToNumber.mappings) {
  //   console.log(`${key} ${value} ${toPaddedReverseBinary(value).join('')}`)
  // }

  const paddedReverseBinarySuffix = (prb) =>
    prb.length === 0 ? '' : `__${prb.join('')}`;

  let description = [];

  for (const [currentState, currentMark, nextState, ..._instructions] of descriptionWithMarks) {
    if (markToNumber.has(currentMark)) {
      const currentMarkNumber = markToNumber.get(currentMark);
      const prb = toPaddedReverseBinary(currentMarkNumber);

      const recognizeMark = prb.pop();
      const recognizeState = `${currentState}${paddedReverseBinarySuffix(prb)}`;

      let lastState = recognizeState;

      const approachDescriptions = []

      while (prb.length > 0) {
        const approachMark = prb.pop();
        const approachState = `${currentState}${paddedReverseBinarySuffix(prb)}`;

        if (!description.find(([currentState, currentMark]) => currentState === approachState && currentMark == approachMark)) {

          approachDescriptions.unshift([approachState, approachMark, lastState, Move(RIGHT)]);
        } // or can probably break

        lastState = approachState;
      }

      for (const d of approachDescriptions) {
        description.push(d);
      }

      // move back to beginning
      const moveBackToBitZero = times(bits - 1).map(() => Move(LEFT));

      // translated instructions
      const translatedInstructions = flatMap(_instructions, instruction => {
        if (instruction instanceof Move) {
          return times(bits).map(() => instruction);
        } else if (instruction instanceof Write) {
          const markNumber = markToNumber.get(instruction.mark);
          const prb = toPaddedReverseBinary(markNumber);

          return flatMap(prb, bit => [Write(bit), Move(RIGHT)])
            .concat([Move(LEFT)])
            .concat(moveBackToBitZero);
        } else {
          console.log(`Don't know how to binary encode ${instruction}`);
          throw 1;
        }
      });

      // optimize away Move[LEFT], Move[RIGHT] and vice-versa
      const instructions = [...moveBackToBitZero, ...translatedInstructions].reduce(
        (acc, instruction) => {
          if (acc.length === 0) {
            acc.push(instruction);
          } else {
            const last = acc[acc.length - 1];

            if (instruction instanceof Move && last instanceof Move && instruction.direction !== last.direction) {
              acc.pop();
            } else {
              acc.push(instruction);
            }
          }
          return acc;
        },
        []
      );

      description.push([recognizeState, recognizeMark, nextState, ...instructions]);
    }

  }

  const chunk = (array) =>
    Array(Math.ceil(array.length/bits)).fill().map((_,i) => array.slice(i*bits,i*bits+bits));

  const tape = flatMap(
    tapeWithMarks,
    cell => {
      const n = markToNumber.get(cell);
      const rb = toReverseBinary(n);
      const padN = bits - rb.length;

      for (let i = 0; i < padN; ++i) {
        rb.push(0);
      }

      return rb;
    }
  );

  const after = (tape) =>
    chunk(tape)
      .map(fromReverseBinary)
        .map(cell => numberToMark.get(cell));

  // pd('binary:', description)

  console.log(`markToNumber size: ${markToNumber.size}`)

  return {
    description,
    tape,
    after
  };
}

This is a snippet from my book-in-progress Tooling for Turing Machines.