Decorator that turns a Turing Machine with a tape that stretches rightward to infinity, into a Turing Machine with a tape that stretches to infinity in both directions

doubly-infinite-tape.es6

// A decorator that compiles a program written for a bi-directionally
// infinite tape, into a program for a unidirectionally
// infinite tape.
//
// Requires a machine that accepts a description written in quintupes
// [ [currentState, currentMark, nextState, markToWrite, direction], ... ]
//
// The machine it decorates must have properties for LEFT and RIGHT,
// representing the possible moves,and HELT, a conventional special state for
// (what else) halting.
// 
// It returns a new machine that accepts programs for a achine with a tape
// that stretches to infinity in both directions. The programs are identical
// in format, but the behaviour is different.
//
// It doesn't actually alter the machine. Insted, it rewrite the program to
// _emulate_ a bidirectionally infinite Turing Machine by using the odd
// numbered positions on the tape for zero..+∞, and the even numbered
// positions for -1..-∞.
//
// An 'anchor' symbol at zero is used to help it "turn around."
//
// The decorator is, in fact, a compiler, and while it is not a strict proof,
// it is an intuitive demomstration that anything computable by a
// bidirectionally infinite Turing Mchine with multiple marks is also
// computable by a unidirectionally infinite Turing Machine with multiple
// marks.
//
// Another decorator (not shown here) compiles machines with multiple marks into
// machines with just ones and zeros, and yet another compiles machines
// with quintuples into machines with quadrples, showing that all Turing Machines
// have equivalent power.

const doubled = (() => {
  const ANCHOR = Symbol('#');
  const SKIP_ANCHOR = Symbol('skip-anchor');

  function double ({ description: _description, tape: _tape, LEFT, RIGHT, HALT }) {
    const tape = _tape.reduce(
        (tape, cell) => {
          tape.push(cell);
          tape.push(0);
        
          return tape;
        },
        [ANCHOR]
    );
  
    const vocabulary = vocabularyOf({ description: _description, tape: _tape });
  
    const intermediateStateFor = ({state, move}) => `__intermediate_${state.toString()}__${move === LEFT ? 'L' : 'R'}`;
    const turnaroundStateFor = ({state, move}) => `__turnaround_${state.toString()}__${move === LEFT ? 'L' : 'R'}`;
    const negativeStateFor = (state) => `__negative_${state.toString()}`;
    const negativeMoveFor = (move) => move === LEFT ? RIGHT : LEFT;
  
    const description = [
        // move right over the anchor to the original start
        ['SKIP_ANCHOR', ANCHOR, _description[0][0], ANCHOR, RIGHT]
      ];
      
    const syntheticStates = new Set();
  
    for (const [currentState, currentMark, nextState, write, move] of _description) {
      // positive
      const intermediateState = intermediateStateFor({ state: nextState, move });
    
      // original
      description.push([currentState, currentMark, intermediateState, write, move]);
    
      // intermediate
      if (!syntheticStates.has(intermediateState)) {
        for (const mark of vocabulary) {
          description.push([intermediateState, mark, nextState, mark, move]);
        }
        syntheticStates.add(intermediateState);
      }
    
      // turnaround
      if (move === LEFT) {
        const turnaroundState = turnaroundStateFor({ state: nextState, move: RIGHT });
        
        if (!syntheticStates.has(turnaroundState)) {
          const negativeNextState = negativeStateFor(nextState);
        
          description.push([intermediateState, ANCHOR, turnaroundState, ANCHOR, RIGHT]);
        
          for (const mark of vocabulary) {
            description.push([turnaroundState, mark, negativeNextState, mark, RIGHT]);
          }
          syntheticStates.add(turnaroundState)
        }
      }
    
      // negative
      const negativeMove = negativeMoveFor(move);
      const negativeIntermediateState = negativeStateFor(intermediateStateFor({ state: nextState, move: negativeMove }));
      const negativeState = negativeStateFor(currentState);
      const negativeNextState = negativeStateFor(nextState);
    
      //negative of original
      description.push([negativeState, currentMark, negativeIntermediateState, write, negativeMove]);
    
      // negative intermediate
      if (!syntheticStates.has(negativeIntermediateState)) {
        for (const mark of vocabulary) {
          description.push([negativeIntermediateState, mark, negativeNextState, mark, negativeMove]);
        }
        syntheticStates.add(negativeIntermediateState);
      }
    
      // turnaround
      if (negativeMove === LEFT) {
        if (!syntheticStates.has(negativeNextState)) {
          description.push([negativeNextState, ANCHOR, negativeNextState, ANCHOR, RIGHT]);
          syntheticStates.add(negativeNextState)
        }
      }
    }
    
    const after = (tape) => {
      const chunk = (array, size) =>
        Array(Math.ceil(array.length/size)).fill().map((_,i) => array.slice(i*size,i*size+size));
        
      const chunked = chunk(tape.slice(1), 2);
      
      return chunked
                .map(x => x[1] || 0)
                .reverse()
                .concat(
                  chunked
                    .map(x => x[0] || 0)
                )
    }
  
    return { description, tape, after };
  }
  
  return (machine) => {
    const { LEFT, RIGHT, HALT } = machine.constants;
    
    const decoratedMachine = ({ description: _description, tape: _tape }) => {
      const { description, tape, after } = double({ description: _description, tape: _tape, LEFT, RIGHT, HALT });
      
      return after(machine({ description, tape }));
    };
    
    return Object.assign(decoratedMachine, { constants: machine.constants });
  }
})();

example.es6

// This three-state, one-mark busy beaver:

['A', 0, 'B', 1, RIGHT]
['A', 1, 'C', 1, LEFT]
['B', 0, 'A', 1, LEFT]
['B', 1, 'B', 1, RIGHT]
['C', 0, 'B', 1, LEFT]
['C', 1, HALT, 1, RIGHT]

// compiles to:

["SKIP_ANCHOR", ANCHOR, "A", ANCHOR, RIGHT]
["A", 0, "__intermediate_B__R", 1, RIGHT]
["__intermediate_B__R", 1, "B", 1, RIGHT]
["__intermediate_B__R", 0, "B", 0, RIGHT]
["__negative_A", 0, "__negative___intermediate_B__L", 1, LEFT]
["__negative___intermediate_B__L", 1, "__negative_B", 1, LEFT]
["__negative___intermediate_B__L", 0, "__negative_B", 0, LEFT]
["__negative_B", ANCHOR, "__negative_B", ANCHOR, RIGHT]
["A", 1, "__intermediate_C__L", 1, LEFT]
["__intermediate_C__L", 1, "C", 1, LEFT]
["__intermediate_C__L", 0, "C", 0, LEFT]
["__intermediate_C__L", ANCHOR, "__turnaround_C__R", ANCHOR, RIGHT]
["__turnaround_C__R", 1, "__negative_C", 1, RIGHT]
["__turnaround_C__R", 0, "__negative_C", 0, RIGHT]
["__negative_A", 1, "__negative___intermediate_C__R", 1, RIGHT]
["__negative___intermediate_C__R", 1, "__negative_C", 1, RIGHT]
["__negative___intermediate_C__R", 0, "__negative_C", 0, RIGHT]
["B", 0, "__intermediate_A__L", 1, LEFT]
["__intermediate_A__L", 1, "A", 1, LEFT]
["__intermediate_A__L", 0, "A", 0, LEFT]
["__intermediate_A__L", ANCHOR, "__turnaround_A__R", ANCHOR, RIGHT]
["__turnaround_A__R", 1, "__negative_A", 1, RIGHT]
["__turnaround_A__R", 0, "__negative_A", 0, RIGHT]
["__negative_B", 0, "__negative___intermediate_A__R", 1, RIGHT]
["__negative___intermediate_A__R", 1, "__negative_A", 1, RIGHT]
["__negative___intermediate_A__R", 0, "__negative_A", 0, RIGHT]
["B", 1, "__intermediate_B__R", 1, RIGHT]
["__negative_B", 1, "__negative___intermediate_B__L", 1, LEFT]
["C", 0, "__intermediate_B__L", 1, LEFT]
["__intermediate_B__L", 1, "B", 1, LEFT]
["__intermediate_B__L", 0, "B", 0, LEFT]
["__intermediate_B__L", ANCHOR, "__turnaround_B__R", ANCHOR, RIGHT]
["__turnaround_B__R", 1, "__negative_B", 1, RIGHT]
["__turnaround_B__R", 0, "__negative_B", 0, RIGHT]
["__negative_C", 0, "__negative___intermediate_B__R", 1, RIGHT]
["__negative___intermediate_B__R", 1, "__negative_B", 1, RIGHT]
["__negative___intermediate_B__R", 0, "__negative_B", 0, RIGHT]
["C", 1, "__intermediate_HALT__R", 1, RIGHT]
["__intermediate_HALT__R", 1, HALT, 1, RIGHT]
["__intermediate_HALT__R", 0, HALT, 0, RIGHT]
["__negative_C", 1, "__negative___intermediate_HALT__L", 1, LEFT]
["__negative___intermediate_HALT__L", 1, "__negative_HALT", 1, LEFT]
["__negative___intermediate_HALT__L", 0, "__negative_HALT", 0, LEFT]
["__negative_HALT", ANCHOR, "__negative_HALT", ANCHOR, RIGHT]