summaryrefslogtreecommitdiff
path: root/godel/js
diff options
context:
space:
mode:
Diffstat (limited to 'godel/js')
-rw-r--r--godel/js/compiler.js182
-rw-r--r--godel/js/godelWorker.js27
-rw-r--r--godel/js/main.js175
-rw-r--r--godel/js/observable.js14
-rw-r--r--godel/js/parser.js1056
-rw-r--r--godel/js/turing_machine.js72
6 files changed, 1526 insertions, 0 deletions
diff --git a/godel/js/compiler.js b/godel/js/compiler.js
new file mode 100644
index 0000000..e978244
--- /dev/null
+++ b/godel/js/compiler.js
@@ -0,0 +1,182 @@
+class StringBuilder {
+ constructor() {
+ this.stringPieces = [];
+ }
+ add(s) {
+ this.stringPieces.push(s);
+ }
+ build() {
+ return this.stringPieces.join("");
+ }
+}
+
+const compileGoto = (gotoNode, stringBuilder) => {
+ stringBuilder.add(`this.followGoto("${gotoNode.label.symbol}");\nreturn;\n`);
+};
+
+const compileConditional = (conditionalNode, stringBuilder) => {
+ const {
+ variable: { symbol: variable },
+ goto: gotoNode,
+ } = conditionalNode;
+
+ stringBuilder.add(`if (this.get("${variable}") != 0) {\n`);
+ compileGoto(gotoNode, stringBuilder);
+ stringBuilder.add(`}\n`);
+};
+
+const compileAssignment = (assignmentNode, stringBuilder) => {
+ const {
+ variable: { symbol: variable },
+ expr,
+ } = assignmentNode;
+ if (expr.opr) {
+ if (expr.opr == "+") stringBuilder.add(`this.addOne("${variable}");\n`);
+ else if (expr.opr == "-")
+ stringBuilder.add(`this.subtractOne("${variable}");\n`);
+ } else {
+ stringBuilder.add("// noop \n");
+ }
+};
+
+const compileInstruction = (instruction, stringBuilder) => {
+ if (instruction.goto) {
+ compileGoto(instruction.goto, stringBuilder);
+ return; // ignore unreachable addition to instructionPointer
+ }
+
+ if (instruction.conditional) {
+ compileConditional(instruction.conditional, stringBuilder);
+ } else if (instruction.assignment) {
+ compileAssignment(instruction.assignment, stringBuilder);
+ }
+
+ stringBuilder.add("this.instructionPointer++;\n");
+};
+
+const compile = (ast) => {
+ const godelSequence = [];
+
+ const stringBuilder = new StringBuilder();
+ stringBuilder.add(`
+ class Program {
+ constructor() {
+ this.variables = new Map(); // variable -> natural number val
+ this.labelInstructions = new Map(); // labels to instruction indices
+ this.instructions = new Map(); // instruction indices to procedures
+
+ this.instructions.set(0, () => this.main());
+ this.instructionPointer = 0;
+ this.variables.set("Y", 0);
+
+ // -- program-specific state init --
+ this.finalInstruction = ${
+ ast.instructions.length + 1
+ }; // instruction of the implied "exit" label
+ // "E1" is the exit label
+ this.labelInstructions.set("E1", this.finalInstruction);
+ }
+
+ get(variable) {
+ if (!this.variables.has(variable)) {
+ this.variables.set(variable, 0);
+ }
+ return this.variables.get(variable);
+ }
+
+ addOne(variable) {
+ const val = this.get(variable);
+ this.variables.set(variable, val + 1);
+ }
+
+ subtractOne(variable) {
+ const val = this.get(variable);
+ this.variables.set(variable, val - 1);
+ }
+
+ followGoto(label) {
+ this.instructionPointer = this.labelInstructions.get(label);
+ }
+
+ step() {
+ if (!this.isCompleted()) {
+ const procedure = this.instructions.get(this.instructionPointer);
+ procedure();
+
+ }
+ return this.instructionPointer;
+ }
+
+ isCompleted() {
+ return this.instructionPointer == this.finalInstruction;
+ }
+
+ getResult() {
+ return this.variables.get("Y");
+ }
+
+ run(maxIter=500_000) {
+ let iter = 0;
+ while (!this.isCompleted() && (++iter) < maxIter) this.step();
+ if (iter < maxIter) {
+ return this.getResult();
+ }
+ throw new Error("Too many iterations. To resolve, please ask"
+ + " Turing how we can find if a program will halt during compilation.");
+ }
+
+ main() {
+`);
+
+ stringBuilder.add("// -- build label -> instruction map --\n");
+ for (let i = 0; i < ast.instructions.length; i++) {
+ const instruction = ast.instructions[i];
+ godelSequence.push(instruction.godel);
+
+ const line = instruction.instruction;
+ const instructionIdx = i + 1;
+ if (line.label) {
+ const symbol = line.label.symbol;
+ stringBuilder.add(
+ `this.instructions.set(${instructionIdx}, () => this.${symbol}());\n`
+ );
+ stringBuilder.add(
+ `this.labelInstructions.set("${symbol}", ${instructionIdx});\n`
+ );
+ }
+ }
+
+ stringBuilder.add("// -- compiled instructions --\n");
+ for (let i = 0; i < ast.instructions.length; i++) {
+ let instruction = ast.instructions[i].instruction;
+ const instructionIdx = i + 1;
+ if (instruction.label) {
+ const symbol = instruction.label.symbol;
+
+ stringBuilder.add(
+ ` this.followGoto("${symbol}");\n}\n\n${symbol}() {\n`
+ );
+ stringBuilder.add(`this.instructionPointer = ${instructionIdx};\n`);
+ instruction = instruction.instruction;
+ }
+
+ compileInstruction(instruction, stringBuilder);
+ }
+
+ stringBuilder.add(` }\n}\n`);
+ stringBuilder.add("// -- \n");
+ stringBuilder.add("const program = new Program();\n\n");
+ stringBuilder.add("// !! set the initial Snapshot here !!\n");
+ stringBuilder.add('// program.variables.set("X1", 2);\n\n');
+ stringBuilder.add("program.run();\n");
+ stringBuilder.add("console.log(program.variables);\n");
+ stringBuilder.add("program.getResult();\n");
+
+ return {
+ js: js_beautify(stringBuilder.build(), {
+ indent_size: 2,
+ wrap_line_length: 100,
+ }),
+ godelSequence,
+ };
+};
diff --git a/godel/js/godelWorker.js b/godel/js/godelWorker.js
new file mode 100644
index 0000000..594a4ad
--- /dev/null
+++ b/godel/js/godelWorker.js
@@ -0,0 +1,27 @@
+const isPrime = (n) =>
+ !Array(Math.ceil(Math.sqrt(n)))
+ .fill(0)
+ .map((_, i) => i + 2) // first prime is 2
+ .some((i) => n !== i && n % i === 0);
+
+const primesCache = [2];
+const p = (i) => {
+ if (primesCache.length <= i) {
+ let x = primesCache.at(-1);
+ while (primesCache.length <= i) {
+ if (isPrime(++x)) primesCache.push(x);
+ }
+ }
+ return primesCache.at(i - 1);
+};
+
+const computeGodelNumber = (godelSequence) =>
+ godelSequence.reduce((acc, num, i) => {
+ const prime = p(i + 1);
+ return BigInt(acc) * BigInt(prime) ** BigInt(num);
+ }, 1) - BigInt(1);
+
+self.addEventListener("message", (e) => {
+ const godelNumber = computeGodelNumber(e.data);
+ postMessage(godelNumber);
+});
diff --git a/godel/js/main.js b/godel/js/main.js
new file mode 100644
index 0000000..9092d2c
--- /dev/null
+++ b/godel/js/main.js
@@ -0,0 +1,175 @@
+const MESSAGES = {
+ COMPILE: "COMPILE",
+ COMPILE_RESULT: "COMPILE_RESULT",
+ EVAL: "EVAL",
+ EVAL_STATUS: "EVAL_RESULT",
+};
+
+// -- the "real" code --
+
+const state = new Observable();
+
+const prepareSource = (text) => text.replaceAll(/\/\/.*/g, "").trim();
+
+const main = () => {
+ let program;
+
+ state.subscribe((msg) => {
+ if (msg.type == MESSAGES.COMPILE) {
+ const { value } = msg;
+ const source = prepareSource(value);
+
+ try {
+ const ast = parser.parse(source);
+ const { js, godelSequence } = compile(ast);
+
+ state.notify({
+ type: MESSAGES.COMPILE_RESULT,
+ success: true,
+ js,
+ godelSequence,
+ });
+ } catch (e) {
+ console.error(e);
+ state.notify({
+ type: MESSAGES.COMPILE_RESULT,
+ error: e.toString(),
+ });
+ }
+ }
+ if (msg.type == MESSAGES.EVAL) {
+ const source = compiledEditorEl.getValue();
+ try {
+ const result = eval(source);
+ state.notify({
+ type: MESSAGES.EVAL_RESULT,
+ success: true,
+ value: result,
+ });
+ } catch (e) {
+ state.notify({
+ type: MESSAGES.EVAL_RESULT,
+ error: e.toString(),
+ });
+ }
+ }
+ });
+};
+main();
+
+// -- a bit of some hacky ui code --
+
+const codeMirrorConfig = {
+ lineNumbers: true,
+};
+const instructionsEl = document.getElementById("instructions");
+const instructionsEditorEl = CodeMirror.fromTextArea(
+ instructionsEl,
+ codeMirrorConfig
+);
+
+const compileButton = document.getElementById("compile");
+const evalButton = document.getElementById("eval");
+const evalStatusEl = document.getElementById("eval_status");
+const compileStatusEl = document.getElementById("compile_status");
+const compiledEl = document.getElementById("compiled");
+const compiledEditorEl = CodeMirror.fromTextArea(compiledEl, codeMirrorConfig);
+const godelSequenceEl = document.getElementById("godel_sequence");
+const godelNumberEl = document.getElementById("godel_number");
+const godelNumberComputeBtn = document.getElementById("godel_number_comp");
+const copyStateButton = document.getElementById("copy");
+
+// hackily copy the program state and put it in the clipboard
+copyStateButton.addEventListener("click", () => {
+ const instructions = btoa(instructionsEditorEl.getValue());
+
+ navigator.clipboard
+ .writeText(
+ window.location.href.split("?")[0] + `?instructions=${instructions}`
+ )
+ .then(() => alert("copied to clipboard"));
+});
+
+state.subscribe((msg) => {
+ if (msg.type == MESSAGES.COMPILE_RESULT) {
+ evalStatusEl.classList.remove("error");
+ evalStatusEl.classList.remove("success");
+ evalStatusEl.innerHTML = "";
+
+ if (msg.success) {
+ const { js, godelSequence } = msg;
+ compiledEditorEl.setValue(js);
+
+ godelSequenceEl.innerHTML = `[${godelSequence.join(", ")}]`;
+ godelNumberComputeBtn.style.display = "inline";
+
+ compileStatusEl.classList.add("success");
+ compileStatusEl.classList.remove("error");
+ compileStatusEl.innerHTML = `Successful compile at ${new Date().toLocaleString()}!`;
+ } else if (msg.error) {
+ compiledEditorEl.setValue("");
+ godelSequenceEl.innerHTML = "";
+ godelNumberEl.innerHTML = "";
+ godelNumberComputeBtn.style.display = "none";
+
+ compileStatusEl.classList.remove("success");
+ compileStatusEl.classList.add("error");
+ compileStatusEl.innerHTML = msg.error;
+ }
+ }
+});
+
+state.subscribe((msg) => {
+ if (msg.type == MESSAGES.COMPILE_RESULT) {
+ if (msg.success) {
+ const { godelSequence } = msg;
+
+ godelNumberComputeBtn.onclick = () => {
+ godelNumberEl.innerHTML = "working...";
+
+ const worker = new Worker("js/godelWorker.js");
+
+ worker.addEventListener("message", (e) => {
+ const godelNumber = e.data;
+ godelNumberEl.innerHTML = godelNumber.toString();
+ });
+
+ worker.postMessage(godelSequence);
+ };
+ } else if (msg.error) {
+ godelNumberComputeBtn.onclick = () => {};
+ }
+ }
+});
+
+state.subscribe((msg) => {
+ if (msg.type == MESSAGES.EVAL_RESULT) {
+ if (msg.success) {
+ evalStatusEl.classList.add("success");
+ evalStatusEl.classList.remove("error");
+ evalStatusEl.innerHTML = `Result: ${msg.value}`;
+ } else if (msg.error) {
+ evalStatusEl.classList.remove("success");
+ evalStatusEl.classList.add("error");
+ evalStatusEl.innerHTML = msg.error;
+ }
+ }
+});
+
+const urlParams = new URLSearchParams(window.location.search);
+if (urlParams.get("instructions")) {
+ instructionsEditorEl.setValue(atob(urlParams.get("instructions")));
+}
+
+compileButton.addEventListener("click", () => {
+ state.notify({
+ type: MESSAGES.COMPILE,
+ value: instructionsEditorEl.getValue(),
+ });
+});
+
+evalButton.addEventListener("click", () => {
+ state.notify({
+ type: MESSAGES.EVAL,
+ });
+});
diff --git a/godel/js/observable.js b/godel/js/observable.js
new file mode 100644
index 0000000..1299fc6
--- /dev/null
+++ b/godel/js/observable.js
@@ -0,0 +1,14 @@
+class Observable {
+ constructor() {
+ this.observers = [];
+ }
+ subscribe(f) {
+ this.observers.push(f);
+ }
+ unsubscribe(f) {
+ this.observers = this.observers.filter((subscriber) => subscriber !== f);
+ }
+ notify(data) {
+ this.observers.forEach((observer) => observer(data));
+ }
+}
diff --git a/godel/js/parser.js b/godel/js/parser.js
new file mode 100644
index 0000000..808132e
--- /dev/null
+++ b/godel/js/parser.js
@@ -0,0 +1,1056 @@
+parser = /*
+ * Generated by PEG.js 0.10.0.
+ *
+ * http://pegjs.org/
+ */
+(function() {
+ "use strict";
+
+ function peg$subclass(child, parent) {
+ function ctor() { this.constructor = child; }
+ ctor.prototype = parent.prototype;
+ child.prototype = new ctor();
+ }
+
+ function peg$SyntaxError(message, expected, found, location) {
+ this.message = message;
+ this.expected = expected;
+ this.found = found;
+ this.location = location;
+ this.name = "SyntaxError";
+
+ if (typeof Error.captureStackTrace === "function") {
+ Error.captureStackTrace(this, peg$SyntaxError);
+ }
+ }
+
+ peg$subclass(peg$SyntaxError, Error);
+
+ peg$SyntaxError.buildMessage = function(expected, found) {
+ var DESCRIBE_EXPECTATION_FNS = {
+ literal: function(expectation) {
+ return "\"" + literalEscape(expectation.text) + "\"";
+ },
+
+ "class": function(expectation) {
+ var escapedParts = "",
+ i;
+
+ for (i = 0; i < expectation.parts.length; i++) {
+ escapedParts += expectation.parts[i] instanceof Array
+ ? classEscape(expectation.parts[i][0]) + "-" + classEscape(expectation.parts[i][1])
+ : classEscape(expectation.parts[i]);
+ }
+
+ return "[" + (expectation.inverted ? "^" : "") + escapedParts + "]";
+ },
+
+ any: function(expectation) {
+ return "any character";
+ },
+
+ end: function(expectation) {
+ return "end of input";
+ },
+
+ other: function(expectation) {
+ return expectation.description;
+ }
+ };
+
+ function hex(ch) {
+ return ch.charCodeAt(0).toString(16).toUpperCase();
+ }
+
+ function literalEscape(s) {
+ return s
+ .replace(/\\/g, '\\\\')
+ .replace(/"/g, '\\"')
+ .replace(/\0/g, '\\0')
+ .replace(/\t/g, '\\t')
+ .replace(/\n/g, '\\n')
+ .replace(/\r/g, '\\r')
+ .replace(/[\x00-\x0F]/g, function(ch) { return '\\x0' + hex(ch); })
+ .replace(/[\x10-\x1F\x7F-\x9F]/g, function(ch) { return '\\x' + hex(ch); });
+ }
+
+ function classEscape(s) {
+ return s
+ .replace(/\\/g, '\\\\')
+ .replace(/\]/g, '\\]')
+ .replace(/\^/g, '\\^')
+ .replace(/-/g, '\\-')
+ .replace(/\0/g, '\\0')
+ .replace(/\t/g, '\\t')
+ .replace(/\n/g, '\\n')
+ .replace(/\r/g, '\\r')
+ .replace(/[\x00-\x0F]/g, function(ch) { return '\\x0' + hex(ch); })
+ .replace(/[\x10-\x1F\x7F-\x9F]/g, function(ch) { return '\\x' + hex(ch); });
+ }
+
+ function describeExpectation(expectation) {
+ return DESCRIBE_EXPECTATION_FNS[expectation.type](expectation);
+ }
+
+ function describeExpected(expected) {
+ var descriptions = new Array(expected.length),
+ i, j;
+
+ for (i = 0; i < expected.length; i++) {
+ descriptions[i] = describeExpectation(expected[i]);
+ }
+
+ descriptions.sort();
+
+ if (descriptions.length > 0) {
+ for (i = 1, j = 1; i < descriptions.length; i++) {
+ if (descriptions[i - 1] !== descriptions[i]) {
+ descriptions[j] = descriptions[i];
+ j++;
+ }
+ }
+ descriptions.length = j;
+ }
+
+ switch (descriptions.length) {
+ case 1:
+ return descriptions[0];
+
+ case 2:
+ return descriptions[0] + " or " + descriptions[1];
+
+ default:
+ return descriptions.slice(0, -1).join(", ")
+ + ", or "
+ + descriptions[descriptions.length - 1];
+ }
+ }
+
+ function describeFound(found) {
+ return found ? "\"" + literalEscape(found) + "\"" : "end of input";
+ }
+
+ return "Expected " + describeExpected(expected) + " but " + describeFound(found) + " found.";
+ };
+
+ function peg$parse(input, options) {
+ options = options !== void 0 ? options : {};
+
+ var peg$FAILED = {},
+
+ peg$startRuleFunctions = { Program: peg$parseProgram },
+ peg$startRuleFunction = peg$parseProgram,
+
+ peg$c0 = /^[\n]/,
+ peg$c1 = peg$classExpectation(["\n"], false, false),
+ peg$c2 = function(lines) {
+ return { instructions: lines.filter((line) => typeof line !== "string" || line.trim() != "") };
+ },
+ peg$c3 = function(instruction) {
+ let x = 0;
+ let y = 0;
+ if (instruction.label) {
+ x = instruction.label.godel;
+ y = instruction.instruction.godel;
+ } else {
+ y = instruction.godel;
+ }
+ return { instruction, godel: ((2 ** x) * ((2 * y) + 1) - 1) };
+ },
+ peg$c4 = function(label, instruction) {
+ return { label, instruction };
+ },
+ peg$c5 = "[",
+ peg$c6 = peg$literalExpectation("[", false),
+ peg$c7 = "]",
+ peg$c8 = peg$literalExpectation("]", false),
+ peg$c9 = function(label) {
+ return label;
+ },
+ peg$c10 = function(conditional) { return { conditional, godel: conditional.godel }; },
+ peg$c11 = function(assignment) { return { assignment, godel: assignment.godel }; },
+ peg$c12 = function(goto) { return { goto, godel: goto.godel }; },
+ peg$c13 = function(label) {
+ return { label, godel: label.godel + 2 };
+ },
+ peg$c14 = "IF",
+ peg$c15 = peg$literalExpectation("IF", false),
+ peg$c16 = "!=",
+ peg$c17 = peg$literalExpectation("!=", false),
+ peg$c18 = "0",
+ peg$c19 = peg$literalExpectation("0", false),
+ peg$c20 = function(variable, goto) {
+ const y = variable.godel - 1;
+ const x = goto.godel;
+ return { variable, goto, godel: ((2 ** x) * ((2 * y) + 1) - 1) };
+ },
+ peg$c21 = "<-",
+ peg$c22 = peg$literalExpectation("<-", false),
+ peg$c23 = function(variable, expr) {
+ if (expr.left.symbol != variable.symbol) {
+ error("left hand variable must match right hand");
+ }
+ const x = expr.instructionNumber;
+ const y = variable.godel - 1;
+ return { variable, expr, godel: ((2 ** x) * ((2 * y) + 1) - 1) };
+ },
+ peg$c24 = "1",
+ peg$c25 = peg$literalExpectation("1", false),
+ peg$c26 = function(left, opr) {
+ const instructionNumber = { "+" : 1, "-" : 2 }[opr];
+ return { left, opr, instructionNumber };
+ },
+ peg$c27 = function(left) {
+ return { left, instructionNumber: 0 };
+ },
+ peg$c28 = "Y",
+ peg$c29 = peg$literalExpectation("Y", false),
+ peg$c30 = function(symbol) { return { symbol, godel: 1 }; },
+ peg$c31 = "X",
+ peg$c32 = peg$literalExpectation("X", false),
+ peg$c33 = "Z",
+ peg$c34 = peg$literalExpectation("Z", false),
+ peg$c35 = function(symbol, ind) {
+ const index = parseInt(ind);
+ const order = ["X", "Z"];
+ const godel = index * order.length + order.indexOf(symbol);
+ return { symbol: symbol + ind, godel };
+ },
+ peg$c36 = "GOTO",
+ peg$c37 = peg$literalExpectation("GOTO", false),
+ peg$c38 = "+",
+ peg$c39 = peg$literalExpectation("+", false),
+ peg$c40 = "-",
+ peg$c41 = peg$literalExpectation("-", false),
+ peg$c42 = /^[A-E]/,
+ peg$c43 = peg$classExpectation([["A", "E"]], false, false),
+ peg$c44 = function(symbol, ind) {
+ const index = parseInt(ind);
+ const godel = (symbol.charCodeAt(0) - "A".charCodeAt(0) + 1) + 5*(index-1);
+ return { symbol: symbol + ind, godel };
+ },
+ peg$c45 = peg$otherExpectation("integer"),
+ peg$c46 = /^[0-9]/,
+ peg$c47 = peg$classExpectation([["0", "9"]], false, false),
+ peg$c48 = function() { return parseInt(text(), 10); },
+ peg$c49 = peg$otherExpectation("whitespace"),
+ peg$c50 = /^[ \t]/,
+ peg$c51 = peg$classExpectation([" ", "\t"], false, false),
+ peg$c52 = function() { },
+
+ peg$currPos = 0,
+ peg$savedPos = 0,
+ peg$posDetailsCache = [{ line: 1, column: 1 }],
+ peg$maxFailPos = 0,
+ peg$maxFailExpected = [],
+ peg$silentFails = 0,
+
+ peg$result;
+
+ if ("startRule" in options) {
+ if (!(options.startRule in peg$startRuleFunctions)) {
+ throw new Error("Can't start parsing from rule \"" + options.startRule + "\".");
+ }
+
+ peg$startRuleFunction = peg$startRuleFunctions[options.startRule];
+ }
+
+ function text() {
+ return input.substring(peg$savedPos, peg$currPos);
+ }
+
+ function location() {
+ return peg$computeLocation(peg$savedPos, peg$currPos);
+ }
+
+ function expected(description, location) {
+ location = location !== void 0 ? location : peg$computeLocation(peg$savedPos, peg$currPos)
+
+ throw peg$buildStructuredError(
+ [peg$otherExpectation(description)],
+ input.substring(peg$savedPos, peg$currPos),
+ location
+ );
+ }
+
+ function error(message, location) {
+ location = location !== void 0 ? location : peg$computeLocation(peg$savedPos, peg$currPos)
+
+ throw peg$buildSimpleError(message, location);
+ }
+
+ function peg$literalExpectation(text, ignoreCase) {
+ return { type: "literal", text: text, ignoreCase: ignoreCase };
+ }
+
+ function peg$classExpectation(parts, inverted, ignoreCase) {
+ return { type: "class", parts: parts, inverted: inverted, ignoreCase: ignoreCase };
+ }
+
+ function peg$anyExpectation() {
+ return { type: "any" };
+ }
+
+ function peg$endExpectation() {
+ return { type: "end" };
+ }
+
+ function peg$otherExpectation(description) {
+ return { type: "other", description: description };
+ }
+
+ function peg$computePosDetails(pos) {
+ var details = peg$posDetailsCache[pos], p;
+
+ if (details) {
+ return details;
+ } else {
+ p = pos - 1;
+ while (!peg$posDetailsCache[p]) {
+ p--;
+ }
+
+ details = peg$posDetailsCache[p];
+ details = {
+ line: details.line,
+ column: details.column
+ };
+
+ while (p < pos) {
+ if (input.charCodeAt(p) === 10) {
+ details.line++;
+ details.column = 1;
+ } else {
+ details.column++;
+ }
+
+ p++;
+ }
+
+ peg$posDetailsCache[pos] = details;
+ return details;
+ }
+ }
+
+ function peg$computeLocation(startPos, endPos) {
+ var startPosDetails = peg$computePosDetails(startPos),
+ endPosDetails = peg$computePosDetails(endPos);
+
+ return {
+ start: {
+ offset: startPos,
+ line: startPosDetails.line,
+ column: startPosDetails.column
+ },
+ end: {
+ offset: endPos,
+ line: endPosDetails.line,
+ column: endPosDetails.column
+ }
+ };
+ }
+
+ function peg$fail(expected) {
+ if (peg$currPos < peg$maxFailPos) { return; }
+
+ if (peg$currPos > peg$maxFailPos) {
+ peg$maxFailPos = peg$currPos;
+ peg$maxFailExpected = [];
+ }
+
+ peg$maxFailExpected.push(expected);
+ }
+
+ function peg$buildSimpleError(message, location) {
+ return new peg$SyntaxError(message, null, null, location);
+ }
+
+ function peg$buildStructuredError(expected, found, location) {
+ return new peg$SyntaxError(
+ peg$SyntaxError.buildMessage(expected, found),
+ expected,
+ found,
+ location
+ );
+ }
+
+ function peg$parseProgram() {
+ var s0, s1, s2;
+
+ s0 = peg$currPos;
+ s1 = [];
+ s2 = peg$parseProgramInstruction();
+ if (s2 === peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 === peg$FAILED) {
+ if (peg$c0.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c1); }
+ }
+ }
+ }
+ while (s2 !== peg$FAILED) {
+ s1.push(s2);
+ s2 = peg$parseProgramInstruction();
+ if (s2 === peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 === peg$FAILED) {
+ if (peg$c0.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c1); }
+ }
+ }
+ }
+ }
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c2(s1);
+ }
+ s0 = s1;
+
+ return s0;
+ }
+
+ function peg$parseProgramInstruction() {
+ var s0, s1, s2, s3, s4;
+
+ s0 = peg$currPos;
+ s1 = peg$parse_();
+ if (s1 === peg$FAILED) {
+ s1 = null;
+ }
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parseLabeledInstruction();
+ if (s2 === peg$FAILED) {
+ s2 = peg$parseInstruction();
+ }
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parse_();
+ if (s3 === peg$FAILED) {
+ s3 = null;
+ }
+ if (s3 !== peg$FAILED) {
+ if (peg$c0.test(input.charAt(peg$currPos))) {
+ s4 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s4 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c1); }
+ }
+ if (s4 === peg$FAILED) {
+ s4 = null;
+ }
+ if (s4 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c3(s2);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseLabeledInstruction() {
+ var s0, s1, s2, s3;
+
+ s0 = peg$currPos;
+ s1 = peg$parseLabel();
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parseInstruction();
+ if (s3 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c4(s1, s3);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseLabel() {
+ var s0, s1, s2, s3, s4, s5;
+
+ s0 = peg$currPos;
+ if (input.charCodeAt(peg$currPos) === 91) {
+ s1 = peg$c5;
+ peg$currPos++;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c6); }
+ }
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 === peg$FAILED) {
+ s2 = null;
+ }
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parseLABEL_V();
+ if (s3 !== peg$FAILED) {
+ s4 = peg$parse_();
+ if (s4 === peg$FAILED) {
+ s4 = null;
+ }
+ if (s4 !== peg$FAILED) {
+ if (input.charCodeAt(peg$currPos) === 93) {
+ s5 = peg$c7;
+ peg$currPos++;
+ } else {
+ s5 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c8); }
+ }
+ if (s5 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c9(s3);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseInstruction() {
+ var s0, s1;
+
+ s0 = peg$currPos;
+ s1 = peg$parseConditional();
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c10(s1);
+ }
+ s0 = s1;
+ if (s0 === peg$FAILED) {
+ s0 = peg$currPos;
+ s1 = peg$parseAssignment();
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c11(s1);
+ }
+ s0 = s1;
+ if (s0 === peg$FAILED) {
+ s0 = peg$currPos;
+ s1 = peg$parseGoto();
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c12(s1);
+ }
+ s0 = s1;
+ }
+ }
+
+ return s0;
+ }
+
+ function peg$parseGoto() {
+ var s0, s1, s2, s3;
+
+ s0 = peg$currPos;
+ s1 = peg$parseGOTO();
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parseLABEL_V();
+ if (s3 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c13(s3);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseConditional() {
+ var s0, s1, s2, s3, s4, s5, s6, s7, s8, s9;
+
+ s0 = peg$currPos;
+ if (input.substr(peg$currPos, 2) === peg$c14) {
+ s1 = peg$c14;
+ peg$currPos += 2;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c15); }
+ }
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parseVAR();
+ if (s3 !== peg$FAILED) {
+ s4 = peg$parse_();
+ if (s4 === peg$FAILED) {
+ s4 = null;
+ }
+ if (s4 !== peg$FAILED) {
+ if (input.substr(peg$currPos, 2) === peg$c16) {
+ s5 = peg$c16;
+ peg$currPos += 2;
+ } else {
+ s5 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c17); }
+ }
+ if (s5 !== peg$FAILED) {
+ s6 = peg$parse_();
+ if (s6 === peg$FAILED) {
+ s6 = null;
+ }
+ if (s6 !== peg$FAILED) {
+ if (input.charCodeAt(peg$currPos) === 48) {
+ s7 = peg$c18;
+ peg$currPos++;
+ } else {
+ s7 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c19); }
+ }
+ if (s7 !== peg$FAILED) {
+ s8 = peg$parse_();
+ if (s8 !== peg$FAILED) {
+ s9 = peg$parseGoto();
+ if (s9 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c20(s3, s9);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseAssignment() {
+ var s0, s1, s2, s3, s4, s5;
+
+ s0 = peg$currPos;
+ s1 = peg$parseVAR();
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 !== peg$FAILED) {
+ if (input.substr(peg$currPos, 2) === peg$c21) {
+ s3 = peg$c21;
+ peg$currPos += 2;
+ } else {
+ s3 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c22); }
+ }
+ if (s3 !== peg$FAILED) {
+ s4 = peg$parse_();
+ if (s4 !== peg$FAILED) {
+ s5 = peg$parseExpression();
+ if (s5 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c23(s1, s5);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseExpression() {
+ var s0, s1, s2, s3, s4, s5;
+
+ s0 = peg$currPos;
+ s1 = peg$parseVAR();
+ if (s1 !== peg$FAILED) {
+ s2 = peg$parse_();
+ if (s2 !== peg$FAILED) {
+ s3 = peg$parseOPERATION();
+ if (s3 !== peg$FAILED) {
+ s4 = peg$parse_();
+ if (s4 !== peg$FAILED) {
+ if (input.charCodeAt(peg$currPos) === 49) {
+ s5 = peg$c24;
+ peg$currPos++;
+ } else {
+ s5 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c25); }
+ }
+ if (s5 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c26(s1, s3);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ if (s0 === peg$FAILED) {
+ s0 = peg$currPos;
+ s1 = peg$parseVAR();
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c27(s1);
+ }
+ s0 = s1;
+ }
+
+ return s0;
+ }
+
+ function peg$parseVAR() {
+ var s0, s1, s2, s3;
+
+ s0 = peg$currPos;
+ if (input.charCodeAt(peg$currPos) === 89) {
+ s1 = peg$c28;
+ peg$currPos++;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c29); }
+ }
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c30(s1);
+ }
+ s0 = s1;
+ if (s0 === peg$FAILED) {
+ s0 = peg$currPos;
+ if (input.charCodeAt(peg$currPos) === 88) {
+ s1 = peg$c31;
+ peg$currPos++;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c32); }
+ }
+ if (s1 === peg$FAILED) {
+ if (input.charCodeAt(peg$currPos) === 90) {
+ s1 = peg$c33;
+ peg$currPos++;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c34); }
+ }
+ }
+ if (s1 !== peg$FAILED) {
+ s2 = [];
+ s3 = peg$parseInteger();
+ if (s3 !== peg$FAILED) {
+ while (s3 !== peg$FAILED) {
+ s2.push(s3);
+ s3 = peg$parseInteger();
+ }
+ } else {
+ s2 = peg$FAILED;
+ }
+ if (s2 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c35(s1, s2);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ }
+
+ return s0;
+ }
+
+ function peg$parseGOTO() {
+ var s0;
+
+ if (input.substr(peg$currPos, 4) === peg$c36) {
+ s0 = peg$c36;
+ peg$currPos += 4;
+ } else {
+ s0 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c37); }
+ }
+
+ return s0;
+ }
+
+ function peg$parseOPERATION() {
+ var s0;
+
+ if (input.charCodeAt(peg$currPos) === 43) {
+ s0 = peg$c38;
+ peg$currPos++;
+ } else {
+ s0 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c39); }
+ }
+ if (s0 === peg$FAILED) {
+ if (input.charCodeAt(peg$currPos) === 45) {
+ s0 = peg$c40;
+ peg$currPos++;
+ } else {
+ s0 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c41); }
+ }
+ }
+
+ return s0;
+ }
+
+ function peg$parseLABEL_V() {
+ var s0, s1, s2, s3;
+
+ s0 = peg$currPos;
+ if (peg$c42.test(input.charAt(peg$currPos))) {
+ s1 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c43); }
+ }
+ if (s1 !== peg$FAILED) {
+ s2 = [];
+ s3 = peg$parseInteger();
+ if (s3 !== peg$FAILED) {
+ while (s3 !== peg$FAILED) {
+ s2.push(s3);
+ s3 = peg$parseInteger();
+ }
+ } else {
+ s2 = peg$FAILED;
+ }
+ if (s2 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c44(s1, s2);
+ s0 = s1;
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+ } else {
+ peg$currPos = s0;
+ s0 = peg$FAILED;
+ }
+
+ return s0;
+ }
+
+ function peg$parseInteger() {
+ var s0, s1, s2;
+
+ peg$silentFails++;
+ s0 = peg$currPos;
+ s1 = [];
+ if (peg$c46.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c47); }
+ }
+ if (s2 !== peg$FAILED) {
+ while (s2 !== peg$FAILED) {
+ s1.push(s2);
+ if (peg$c46.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c47); }
+ }
+ }
+ } else {
+ s1 = peg$FAILED;
+ }
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c48();
+ }
+ s0 = s1;
+ peg$silentFails--;
+ if (s0 === peg$FAILED) {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c45); }
+ }
+
+ return s0;
+ }
+
+ function peg$parse_() {
+ var s0, s1, s2;
+
+ peg$silentFails++;
+ s0 = peg$currPos;
+ s1 = [];
+ if (peg$c50.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c51); }
+ }
+ if (s2 !== peg$FAILED) {
+ while (s2 !== peg$FAILED) {
+ s1.push(s2);
+ if (peg$c50.test(input.charAt(peg$currPos))) {
+ s2 = input.charAt(peg$currPos);
+ peg$currPos++;
+ } else {
+ s2 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c51); }
+ }
+ }
+ } else {
+ s1 = peg$FAILED;
+ }
+ if (s1 !== peg$FAILED) {
+ peg$savedPos = s0;
+ s1 = peg$c52();
+ }
+ s0 = s1;
+ peg$silentFails--;
+ if (s0 === peg$FAILED) {
+ s1 = peg$FAILED;
+ if (peg$silentFails === 0) { peg$fail(peg$c49); }
+ }
+
+ return s0;
+ }
+
+ peg$result = peg$startRuleFunction();
+
+ if (peg$result !== peg$FAILED && peg$currPos === input.length) {
+ return peg$result;
+ } else {
+ if (peg$result !== peg$FAILED && peg$currPos < input.length) {
+ peg$fail(peg$endExpectation());
+ }
+
+ throw peg$buildStructuredError(
+ peg$maxFailExpected,
+ peg$maxFailPos < input.length ? input.charAt(peg$maxFailPos) : null,
+ peg$maxFailPos < input.length
+ ? peg$computeLocation(peg$maxFailPos, peg$maxFailPos + 1)
+ : peg$computeLocation(peg$maxFailPos, peg$maxFailPos)
+ );
+ }
+ }
+
+ return {
+ SyntaxError: peg$SyntaxError,
+ parse: peg$parse
+ };
+})();
diff --git a/godel/js/turing_machine.js b/godel/js/turing_machine.js
new file mode 100644
index 0000000..a61b43a
--- /dev/null
+++ b/godel/js/turing_machine.js
@@ -0,0 +1,72 @@
+class TuringMachine {
+ constructor(tape = [], rules = [], initialState = "q0", acceptState = "f") {
+ this.tape = tape;
+ this.rules = this.parseRules(rules);
+ this.state = initialState;
+ this.head = 0;
+ this.acceptState = acceptState;
+
+ this.iteration = 0;
+ }
+
+ getStateStatus() {
+ return `State: ${this.state}, Step: ${this.iteration}`;
+ }
+
+ getHead() {
+ return this.head;
+ }
+
+ getState() {
+ return this.state;
+ }
+
+ getTapeAtCell(idx) {
+ return this.tape[idx];
+ }
+
+ setTapeAtCell(idx, val) {
+ this.tape[idx] = val;
+ }
+
+ isAccepting() {
+ return this.state == this.acceptState;
+ }
+
+ parseRules(rules) {
+ const parsedRules = {};
+ for (const [currentState, readSymbol, action, newState] of rules) {
+ const key = `${currentState},${readSymbol}`;
+ const value = `${newState},${action}`;
+ parsedRules[key] = value;
+ }
+ return parsedRules;
+ }
+
+ step() {
+ const currentSymbol = this.tape[this.head];
+ const key = `${this.state},${currentSymbol}`;
+ if (!(key in this.rules)) {
+ return false;
+ }
+ const rule = this.rules[key];
+ const [newState, action] = rule.split(",");
+
+ this.state = newState;
+ this.iteration++;
+
+ if (action === "R") {
+ this.head += 1;
+ } else if (action === "L") {
+ this.head -= 1;
+ } else {
+ this.tape[this.head] = action;
+ }
+
+ if (this.isAccepting()) {
+ return false;
+ }
+
+ return this.head >= 0 && this.head < this.tape.length;
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-22 02:08:17 +0000