src/toys/turing/js/machine.js


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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;
  }
}