initial turing machine

author: Elizabeth Hunt <elizabeth.hunt@simponic.xyz> 2023-10-24 22:28:40 -0600
committer: Elizabeth Hunt <elizabeth.hunt@simponic.xyz> 2023-10-24 22:28:40 -0600
commit: 4ce505b125950521860f0d2170409719927f3f85 (patch)
tree: fc5d256d0c7bc1403c648c617b4e0d17416e4877
parent: d6b885b318f68f9be19fd3dcc4d77e0f30f25ff5 (diff)
download: simponic.xyz-4ce505b125950521860f0d2170409719927f3f85.tar.gz
simponic.xyz-4ce505b125950521860f0d2170409719927f3f85.zip
6 files changed, 361 insertions, 45 deletions
diff --git a/index.html b/index.html
index d5c54de..1bea721 100644
--- a/index.html
+++ b/index.html
@@ -23,6 +23,9 @@
         <br />
         📖 This page hosts strictly static content.
         <br />
+        🐙 Obviously my GitHub is at
+        <a href="https://github.com/Simponic">/simponic</a>.
+        <br />
         🔔 My "real website" is at
         <a href="https://simponic.xyz">simponic.xyz</a>.
       </h3>
@@ -35,8 +38,8 @@
           <div class="project-body">
             <h1>Euler Golf 2</h1>
             <p>
-              A puzzle game (with BFS solver) to explore rotations in the complex
-              plane.
+              A puzzle game (with BFS solver) to explore rotations in the
+              complex plane.
             </p>
           </div>
         </a>
@@ -77,8 +80,8 @@
           <div class="project-body">
             <h1>The A-maze-ing Maize Maze</h1>
             <p>
-              A Randomized Kruskal's Maze game with (more) BFS. You play
-              as a 🌽corn stalk trying to become 🍿popcorn.
+              A Randomized Kruskal's Maze game with (more) BFS. You play as a
+              🌽corn stalk trying to become 🍿popcorn.
             </p>
           </div>
         </a>
@@ -90,9 +93,7 @@
 
           <div class="project-body">
             <h1>Centipede</h1>
-            <p>
-              Boring remake of the classic arcade game.
-            </p>
+            <p>Boring remake of the classic arcade game.</p>
           </div>
         </a>
 
diff --git a/turing-machine/css/styles.css b/turing-machine/css/styles.css
index 02279e5..a345f51 100644
--- a/turing-machine/css/styles.css
+++ b/turing-machine/css/styles.css
@@ -1,5 +1,6 @@
 * {
   font-family: "Trebuchet MS", sans-serif;
+  margin: 0;
 }
 
 button {
@@ -24,11 +25,15 @@ body {
   margin-left: auto;
   margin-right: auto;
   flex-direction: column;
+  gap: 1rem;
 
   padding: 2rem;
 }
 
 .tape {
+  border-radius: 0.25rem;
+  box-shadow: 5px 5px 5px #666666;
+
   display: flex;
 
   padding: 1rem;
@@ -39,16 +44,19 @@ body {
   height: 5rem;
   max-width: 100%;
 
-  border: 1px solid black;
+  border: 2px solid white;
 
   overflow-x: scroll;
   overflow-y: hidden;
 }
 
 .cell {
+  border-radius: 0.25rem;
+  box-shadow: 2px 2px 5px #666666;
+  background-color: #dddddd;
+
   position: relative;
   height: 80%;
-  border: 3px solid black;
   transition: border 0.1s ease-in-out;
   transition: background 0.1s ease-in-out;
 
@@ -85,6 +93,40 @@ body {
 }
 
 .cell-input {
+  border: none;
+  border-radius: 0.25rem;
+
+  background-color: 1px solid #ccc;
   width: 50px;
+  margin-left: 0.25rem;
+  margin-right: 0.25rem;
+
   text-align: center;
+  font-size: 1rem;
+}
+
+textarea {
+  border-radius: 0.25rem;
+  height: 50vh;
+}
+
+.error {
+  color: red;
+}
+
+.success {
+  color: green;
+}
+
+.controls {
+  display: flex;
+  gap: 1rem;
+  flex-direction: row;
+  justify-content: center;
+  align-items: center;
+}
+
+hr {
+  border-top: 2px solid black;
+  border-bottom: none;
 }
diff --git a/turing-machine/index.html b/turing-machine/index.html
index 2f65aa3..acc1e74 100644
--- a/turing-machine/index.html
+++ b/turing-machine/index.html
@@ -7,8 +7,23 @@
 <body>
   <div class="container">
     <h1>Simponic's State System</h1>
+    <p>Author: Elizabeth Hunt</p>
+    <hr>
+    <p id="turing_state">State: _</p>
     <div id="tape" class="tape"></div>
+    <div class="controls" id="controls" style="display: none">
+      <button id="next_step">Next Step</button> <button id=
+      "toggle_play">🔁 Begin</button> <button id=
+      "reset">Reset</button><br>
+    </div>
+    <textarea id="instructions">test</textarea>
+    <div>
+      <button id="compile">Compile</button><span style=
+      "margin-left: 0.5rem" id="compile_status"></span>
+    </div>
   </div>
+  <script src="js/observable.js"></script> 
+  <script src="js/turing_machine.js"></script> 
   <script src="js/main.js"></script>
 </body>
 </html>
diff --git a/turing-machine/js/main.js b/turing-machine/js/main.js
index 68aaa39..9ace6f4 100644
--- a/turing-machine/js/main.js
+++ b/turing-machine/js/main.js
@@ -1,51 +1,24 @@
-const DISPLAY_CELLS = 15;
-const TAPE_LEN = 200;
-
 const MESSAGES = {
   SET_CELL: "SET_CELL",
   PAUSE: "PAUSE",
   SIMULATE: "SIMULATE",
   SET_READER: "SET_READER",
+  NEXT_STEP: "NEXT_STEP",
+  COMPILE: "COMPILE",
+  COMPILE_STATUS: "COMPILE_STATUS",
+  NEW_TURING_STATE: "NEW_TURING_STATE",
 };
 
-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));
-  }
-}
-
 const state = new Observable();
 
-const tape = Array(TAPE_LEN).fill(0);
-state.subscribe((msg) => {
-  if (msg.type == MESSAGES.SET_CELL) {
-    tape[msg.cellId] = msg.value;
-  }
-});
-
-const tapeEl = document.getElementById("tape");
-
 const inputCellId = (cellId) => `${cellId}-input`;
-const updateCellButtonId = (cellId) => `${cellId}-button-update`;
 
 const setCellFromInput = (cellId, inputId) => {
   const input = document.getElementById(inputId);
   tape[cellId] = input.value;
 };
 
-const cell = (cellId, initValue = 0) => {
+const cell = (cellId, initValue = "NULL") => {
   const cellDiv = document.createElement("div");
   cellDiv.classList.add("cell");
   cellDiv.id = cellId;
@@ -85,14 +58,203 @@ const cell = (cellId, initValue = 0) => {
   return cellDiv;
 };
 
+const parseRules = (rules, beginState) => {
+  const quadruples = rules.split("\n");
+
+  const instructions = [];
+  quadruples.forEach((quadruple, line) => {
+    const commentLess = quadruple.replaceAll(/\/\/.*/g, "").trim();
+    if (!commentLess) {
+      return;
+    }
+
+    const items = commentLess
+      .split(" ")
+      .map((x) => x.trim())
+      .filter((x) => x);
+    if (items.length != 4) {
+      throw new Error(`Invalid instruction on line ${line}`);
+    }
+    instructions.push(items);
+  });
+  if (!instructions.some(([fromState]) => fromState == beginState)) {
+    throw new Error(
+      `At least one instruction must begin from state: ${beginState}`
+    );
+  }
+  return instructions;
+};
+
+// --
+
+const tapeEl = document.getElementById("tape");
+const compileButton = document.getElementById("compile");
+const instructionsEl = document.getElementById("instructions");
+const controlsEl = document.getElementById("controls");
+const nextStepButton = document.getElementById("next_step");
+const togglePlayButton = document.getElementById("toggle_play");
+const compileStatusEl = document.getElementById("compile_status");
+const turingMachineStateEl = document.getElementById("turing_state");
+const resetButton = document.getElementById("reset");
+
+resetButton.addEventListener("click", () => {
+  state.notify({ type: MESSAGES.PAUSE });
+  state.notify({ type: MESSAGES.COMPILE, value: instructionsEl.value });
+});
+
+compileButton.addEventListener("click", () => {
+  state.notify({ type: MESSAGES.COMPILE, value: instructionsEl.value });
+});
+
+nextStepButton.addEventListener("click", () => {
+  state.notify({ type: MESSAGES.PAUSE });
+  state.notify({ type: MESSAGES.NEXT_STEP });
+});
+
+let playButton_simulationStatus = "paused";
+togglePlayButton.addEventListener("click", function () {
+  if (playButton_simulationStatus == "paused") {
+    state.notify({ type: MESSAGES.SIMULATE });
+  } else if (playButton_simulationStatus == "simulate") {
+    state.notify({ type: MESSAGES.PAUSE });
+  }
+});
+
+state.subscribe((msg) => {
+  if (msg.type == MESSAGES.COMPILE_STATUS) {
+    const { error, success } = msg;
+    if (error) {
+      compileStatusEl.classList.remove("success");
+      compileStatusEl.classList.add("error");
+      compileStatusEl.innerHTML = error;
+    }
+    if (success) {
+      compileStatusEl.classList.add("success");
+      compileStatusEl.classList.remove("error");
+      compileStatusEl.innerHTML = `Successful compile at ${new Date().toLocaleString()}!`;
+    }
+  }
+});
+
+state.subscribe((msg) => {
+  if (msg.type == MESSAGES.COMPILE_STATUS) {
+    const { error, success } = msg;
+    if (error) {
+      controlsEl.style.display = "none";
+    } else if (success) {
+      controlsEl.style.display = "block";
+    }
+  }
+});
+
+state.subscribe((msg) => {
+  if (msg.type == MESSAGES.PAUSE) {
+    togglePlayButton.innerHTML = "🔁 Begin";
+    playButton_simulationStatus = "paused";
+  }
+  if (msg.type == MESSAGES.SIMULATE) {
+    togglePlayButton.innerHTML = "⏸️ Pause";
+    playButton_simulationStatus = "simulate";
+  }
+});
+
+state.subscribe((msg) => {
+  if (msg.type == MESSAGES.NEW_TURING_STATE) {
+    turingMachineStateEl.innerHTML = msg.value;
+  }
+});
+
+// -
+
 const main = () => {
-  const cells = tape.map((_, cellId) => cell(cellId));
+  const blank = "B";
+  const beginState = "q0";
+  const acceptState = "f";
+  const tape = Array(200).fill(blank);
+  const cells = tape.map((_, cellId) => cell(cellId, blank));
   for (const cell of cells) {
     tapeEl.appendChild(cell);
   }
-  state.notify({ type: MESSAGES.SET_READER, cell: 0 });
 
-  setTimeout(() => {}, 1000);
-};
+  let turingMachine;
+
+  state.subscribe((msg) => {
+    if (msg.type == MESSAGES.SET_CELL) {
+      const { value, cell } = msg;
+      tape[cell] = value;
+      if (turingMachine) turingMachine.setTapeAtCell(cell, value);
+    }
+    if (msg.type == MESSAGES.COMPILE) {
+      const { value } = msg;
+      try {
+        const rules = parseRules(value, beginState, acceptState);
+
+        turingMachine = new TuringMachine(
+          [...tape],
+          rules,
+          beginState,
+          blank,
+          acceptState
+        );
+        state.notify({ type: MESSAGES.SET_READER, cell: 0 });
+        state.notify({
+          type: MESSAGES.NEW_TURING_STATE,
+          value: turingMachine.getStateStatus(),
+        });
+        state.notify({ type: MESSAGES.COMPILE_STATUS, success: true });
+      } catch (e) {
+        state.notify({ type: MESSAGES.COMPILE_STATUS, error: e.toString() });
+      }
+    }
+    if (msg.type == MESSAGES.SIMULATE) {
+      const interval = setInterval(() => {
+        state.notify({ type: MESSAGES.NEXT_STEP });
+      }, 300);
+      const subscriptionFn = (msg) => {
+        if (msg.type == MESSAGES.PAUSE) {
+          clearInterval(interval);
+          state.unsubscribe(subscriptionFn);
+        }
+      };
+      state.subscribe(subscriptionFn);
+    }
+    if (msg.type == MESSAGES.NEXT_STEP && turingMachine) {
+      const step = turingMachine.step();
+
+      const status = turingMachine.getStateStatus();
 
+      const cell = turingMachine.getHead();
+
+      if (!step) {
+        const accepting = turingMachine.isAccepting();
+        state.notify({
+          type: MESSAGES.NEW_TURING_STATE,
+          value: accepting
+            ? `<span class='success'>Accept(${status})</span>`
+            : `<span class='error'>Fail(${status}}</span>`,
+        });
+      } else {
+        state.notify({
+          type: MESSAGES.NEW_TURING_STATE,
+          value: status,
+        });
+      }
+
+      state.notify({
+        type: MESSAGES.SET_READER,
+        cell,
+      });
+      state.notify({
+        type: MESSAGES.SET_CELL,
+        cell,
+        value: turingMachine.getTapeAtCell(cell),
+      });
+
+      if (!step)
+        state.notify({
+          type: MESSAGES.PAUSE,
+        });
+    }
+  });
+};
 main();
diff --git a/turing-machine/js/observable.js b/turing-machine/js/observable.js
new file mode 100644
index 0000000..1299fc6
--- /dev/null
+++ b/turing-machine/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/turing-machine/js/turing_machine.js b/turing-machine/js/turing_machine.js
new file mode 100644
index 0000000..9c21983
--- /dev/null
+++ b/turing-machine/js/turing_machine.js
@@ -0,0 +1,82 @@
+class TuringMachine {
+  constructor(
+    tape = [],
+    rules = [],
+    initialState = "q0",
+    blankSymbol = "B",
+    acceptState = "f"
+  ) {
+    this.tape = tape;
+    this.rules = this.parseRules(rules);
+    this.state = initialState;
+    this.head = 0;
+    this.blankSymbol = blankSymbol;
+    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] || this.blankSymbol;
+    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;
+
+    if (action === "R") {
+      this.head += 1;
+    } else if (action === "L") {
+      this.head -= 1;
+    } else {
+      this.tape[this.head] = action;
+    }
+
+    if (this.isAccepting()) {
+      return false;
+    }
+
+    if (this.head >= 0 && this.head < this.tape.length) {
+      this.iteration++;
+      return true;
+    }
+    return false;
+  }
+}
author	Elizabeth Hunt <elizabeth.hunt@simponic.xyz>	2023-10-24 22:28:40 -0600
committer	Elizabeth Hunt <elizabeth.hunt@simponic.xyz>	2023-10-24 22:28:40 -0600
commit	4ce505b125950521860f0d2170409719927f3f85 (patch)
tree	fc5d256d0c7bc1403c648c617b4e0d17416e4877
parent	d6b885b318f68f9be19fd3dcc4d77e0f30f25ff5 (diff)
download	simponic.xyz-4ce505b125950521860f0d2170409719927f3f85.tar.gz simponic.xyz-4ce505b125950521860f0d2170409719927f3f85.zip