Skip to content

Instantly share code, notes, and snippets.

@raganwald
Created September 25, 2023 15:54
Show Gist options
  • Save raganwald/ca6d6b30ed7646a45d5a57f15b11e0a3 to your computer and use it in GitHub Desktop.
Save raganwald/ca6d6b30ed7646a45d5a57f15b11e0a3 to your computer and use it in GitHub Desktop.
A Magnificent Minsky Machine that determines whether a natural number halts
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(', ')
);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment