Adding some of my favorite toys

1 files changed, 75 insertions, 0 deletions

diff --git a/src/toys/turing/js/machine.js b/src/toys/turing/js/machine.js
new file mode 100644
index 0000000..6af4be6
--- /dev/null
+++ b/src/toys/turing/js/machine.js
@@ -0,0 +1,75 @@
+export class TuringMachine {
+  constructor({
+    tape,
+    rules,
+    startState,
+    acceptStates = [],
+    rejectStates = []
+  }) {
+    this.tape = tape;
+    this.rules = rules;
+    this.state = startState;
+    this.acceptStates = new Set(acceptStates);
+    this.rejectStates = new Set(rejectStates);
+    this.iteration = 0;
+  }
+
+  step() {
+    if (this.isHalted()) {
+      return false;
+    }
+
+    const currentSymbol = this.tape.readHead();
+    const ruleKey = this.getRuleKey(this.state, currentSymbol);
+    if (!this.rules.has(ruleKey)) {
+      return false;
+    }
+
+    const { nextState, writeSymbol, direction } = this.rules.get(ruleKey);
+    this.tape.writeHead(writeSymbol);
+
+    if (direction === "R") {
+      this.tape.moveRight();
+    } else if (direction === "L") {
+      this.tape.moveLeft();
+    }
+
+    this.state = nextState;
+    this.iteration += 1;
+    return !this.isHalted();
+  }
+
+  canStep() {
+    if (this.isHalted()) {
+      return false;
+    }
+
+    const currentSymbol = this.tape.readHead();
+    const ruleKey = this.getRuleKey(this.state, currentSymbol);
+    return this.rules.has(ruleKey);
+  }
+
+  getRuleKey(state, symbol) {
+    return `${state}:${symbol}`;
+  }
+
+  isAccepting() {
+    return this.acceptStates.has(this.state);
+  }
+
+  isRejecting() {
+    return this.rejectStates.has(this.state);
+  }
+
+  isHalted() {
+    return this.isAccepting() || this.isRejecting();
+  }
+
+  getStateStatus() {
+    return `State: ${this.state}, Step: ${this.iteration}`;
+  }
+
+  getState() {
+    return this.state;
+  }
+}