A Magnificent Minsky Machine that determines whether a natural number halts

collatz-minky.js

const truncated = a => {
  let aa = [...a];
  
  while (aa.length > 1 && (aa[aa.length - 1] === 0 || aa[aa.length - 1] == null)) {
    aa = aa.slice(0, aa.length - 1);
  }
  
  return aa;
}

const parse = (program) => {
  const stripComments = program => {
    const lines = program.split("\n");
    const linesAndComments = lines.map(line => line.split("//"));
    const justlines = linesAndComments.map ( lc => lc[0] );
    const strippedProgram = justlines.join("\n");
  
    return strippedProgram;
  }
  const parseProgram = program => program.split(/\s*;\s*/).map(s => s.trim());
  const parseState = state => state.split(/(?:\s*,|\s)\s*/).map(s => s.trim());
  const parseRule = (rule, stateIndex) => {
    const [clauses, nextState] = rule.includes('→') ? rule.split(/\s*→\s*/).map(s => s.trim()) : [rule.trim(), stateIndex + 1]

    return [clauses, typeof nextState === 'string' ? parseInt(nextState, 10) : nextState];
  };
  const parseClauses = clauses => clauses.split('/').map(s => s.trim());
  const parseClause = clause => {
    if (clause === '') return [];

    const strippedClause = clause.substring(1, clause.length - 1); // strip opening and closing ()
    const pairs = strippedClause.split(/\)\s*\(/).map(s => s.trim());

    return pairs.map(p => p.split(/\s*\^\s*/).map(s => parseInt(s, 10)));
  };

  return [[]].concat(
    parseProgram(stripComments(program)).map(
      (state, stateIndex) => parseState(state).map(
        rule => {
          const [_clauses, nextState] = parseRule(rule, stateIndex);
          const clauses = parseClauses(_clauses).map(parseClause);

          return clauses.concat([nextState]);
        }
      )
    )
  );
}

const interpret = (parsed, input = []) => {
  const tapes = ['ANCHOR', ...input]; // fake 1-indexing

  let stateIndex = 1;

  run: while (stateIndex > 0 && stateIndex < parsed.length) {
    const rules = parsed[stateIndex];
    
    const tt = truncated(tapes.slice(1));
    
    if (tt.length === 1) {
      console.log(tt.join(', '));
    }
    
    for (const [actionClauses, guardClauses, nextState] of rules) {
      if (guardClauses.some(
        ([tapeIndex, squares]) => tapes[tapeIndex] === undefined || tapes[tapeIndex] < squares
      )) continue;
      for (const [tapeIndex, squares] of guardClauses) {
        tapes[tapeIndex] = tapes[tapeIndex] - squares;
      }
      for (const [tapeIndex, squares] of actionClauses) {
        tapes[tapeIndex] = (tapes[tapeIndex] || 0) + squares;
      }
      stateIndex = nextState;
      continue run;
    }
    break;
  }

  const output = tapes.slice(1); // unfake 1-indexing

  return output;
}

const evaluate = (program, ...tapes) => interpret(parse(program), tapes);

console.log('START');

console.log(
truncated(evaluate(
`
// flag 11 even number
// adds one to one, then bridges to flag 12
(1^1)(12^1)/(11^1)

// flag 12 sets flag 11 if there are one or more in two
(11^1)/(2^1)(12^1)
// else shuts down and we start all over again
(1^0)/(12^1)

// flag 9 n was an odd number >= 3
// start state:
//   register 1 is zero
//   register 2 is (n-3)/2 (3->0, 5->1, 7->2, &c.)
//
// the final state we want is (3n + 1)/2
// 3n+1 must be even, and we can use this to cut our computation roughly in half
// 
// (3n + 1)/2 -> 3n/2 + 1/2
//            -> 3(n-1)/2 + 3*1/2 + 1/2
//            -> 3(n-1)/2 + 2
//            -> 3(n-3)/2 + 3 + 2
//            -> 3 * r2 + 5

// first, copy five, bridge to flag 9
(1^5)(9^1)/(8^1)

// second, copy three for one repeatedly, bridging to flag 10
(1^3)(10^1)/(9^1)(2^1)
// or clear the flag, ending it all
(1^0)/(9^1)

// ten to nine bridge
(9^1)/(10^1)

// start here
(2^1)/(1^2) // register[2] = register[1] / 2

// odd number greater than one:
// set flag eight, remove last bit
(8^1)/(1^1)(2^1)

(11^1)/(2^1) // else set flag 11 if even and greater than one
`, 6453)).join(', ')
);