turing-machine-simulator

Simulate a deterministic Turing Machine through the Node.js REPL

examples

multiplying two numbers

Multiply two numbers, a and b, where the numbers are represented by zeroes and the multiplication operator is represented by 1.

For example, multiplying 2 by 3 is represented by 001000.

Transitions:

{
    q0: [["0", "0", "R", "q0"], ["1", "1", "R", "q0"], ["_", "$", "L", "q1"]],
    q1: [["0", "0", "L", "q1"], ["1", "1", "L", "q1"], ["_", "_", "R", "q2"]],
    q2: [["0", "0", "R", "q2"], ["1", "1", "R", "q3"]],
    q3: [["Y", "Y", "R", "q3"], ["0", "Y", "L", "q4"], ["$", "_", "L", "q8"]],
    q4: [["0", "0", "L", "q4"], ["1", "1", "L", "q4"], ["X", "X", "L", "q4"], ["Y", "Y", "L", "q4"], ["$", "$", "L", "q4"], ["_", "_", "R", "q5"]],
    q5: [["X", "X", "R", "q5"], ["0", "X", "R", "q6"], ["1", "1", "L", "q7"]],
    q6: [["0", "0", "R", "q6"], ["1", "1", "R", "q6"], ["Y", "Y", "R", "q6"], ["$", "$", "R", "q6"], ["_", "0", "L", "q4"]],
    q7: [["X", "0", "L", "q7"], ["_", "_", "R", "q2"]],
    q8: [["0", "_", "L", "q8"], ["1", "_", "L", "q8"], ["X", "_", "L", "q8"], ["Y", "_", "L", "q8"], ["_", "_", "R", "q9"]],
    q9: []
}

Inputs:

1. 001000
2. 000100
3. 00001000
4. 100
5. 001

example output

Scenario: Multiplying two numbers

                              ↓
                             _0010_

                               ↓
δ(q0 0) → δ(0 R q0)          _0010_

                                ↓
δ(q0 0) → δ(0 R q0)          _0010_

                                 ↓
δ(q0 1) → δ(1 R q0)          _0010_

                                  ↓
δ(q0 0) → δ(0 R q0)          _0010__

                                 ↓
δ(q0 _) → δ($ L q1)          _0010$_

                                ↓
δ(q1 0) → δ(0 L q1)          _0010$_

                               ↓
δ(q1 1) → δ(1 L q1)          _0010$_

                              ↓
δ(q1 0) → δ(0 L q1)          _0010$_

                              ↓
δ(q1 0) → δ(0 L q1)          __0010$_

                               ↓
δ(q1 _) → δ(_ R q2)          __0010$_

                                ↓
δ(q2 0) → δ(0 R q2)          __0010$_

                                 ↓
δ(q2 0) → δ(0 R q2)          __0010$_

                                  ↓
δ(q2 1) → δ(1 R q3)          __0010$_

                                 ↓
δ(q3 0) → δ(Y L q4)          __001Y$_

                                ↓
δ(q4 1) → δ(1 L q4)          __001Y$_

                               ↓
δ(q4 0) → δ(0 L q4)          __001Y$_

                              ↓
δ(q4 0) → δ(0 L q4)          __001Y$_

                               ↓
δ(q4 _) → δ(_ R q5)          __001Y$_

                                ↓
δ(q5 0) → δ(X R q6)          __X01Y$_

                                 ↓
δ(q6 0) → δ(0 R q6)          __X01Y$_

                                  ↓
δ(q6 1) → δ(1 R q6)          __X01Y$_

                                   ↓
δ(q6 Y) → δ(Y R q6)          __X01Y$_

                                    ↓
δ(q6 $) → δ($ R q6)          __X01Y$__

                                   ↓
δ(q6 _) → δ(0 L q4)          __X01Y$0_

                                  ↓
δ(q4 $) → δ($ L q4)          __X01Y$0_

                                 ↓
δ(q4 Y) → δ(Y L q4)          __X01Y$0_

                                ↓
δ(q4 1) → δ(1 L q4)          __X01Y$0_

                               ↓
δ(q4 0) → δ(0 L q4)          __X01Y$0_

                              ↓
δ(q4 X) → δ(X L q4)          __X01Y$0_

                               ↓
δ(q4 _) → δ(_ R q5)          __X01Y$0_

                                ↓
δ(q5 X) → δ(X R q5)          __X01Y$0_

                                 ↓
δ(q5 0) → δ(X R q6)          __XX1Y$0_

                                  ↓
δ(q6 1) → δ(1 R q6)          __XX1Y$0_

                                   ↓
δ(q6 Y) → δ(Y R q6)          __XX1Y$0_

                                    ↓
δ(q6 $) → δ($ R q6)          __XX1Y$0_

                                     ↓
δ(q6 0) → δ(0 R q6)          __XX1Y$0__

                                    ↓
δ(q6 _) → δ(0 L q4)          __XX1Y$00_

                                   ↓
δ(q4 0) → δ(0 L q4)          __XX1Y$00_

                                  ↓
δ(q4 $) → δ($ L q4)          __XX1Y$00_

                                 ↓
δ(q4 Y) → δ(Y L q4)          __XX1Y$00_

                                ↓
δ(q4 1) → δ(1 L q4)          __XX1Y$00_

                               ↓
δ(q4 X) → δ(X L q4)          __XX1Y$00_

                              ↓
δ(q4 X) → δ(X L q4)          __XX1Y$00_

                               ↓
δ(q4 _) → δ(_ R q5)          __XX1Y$00_

                                ↓
δ(q5 X) → δ(X R q5)          __XX1Y$00_

                                 ↓
δ(q5 X) → δ(X R q5)          __XX1Y$00_

                                ↓
δ(q5 1) → δ(1 L q7)          __XX1Y$00_

                               ↓
δ(q7 X) → δ(0 L q7)          __X01Y$00_

                              ↓
δ(q7 X) → δ(0 L q7)          __001Y$00_

                               ↓
δ(q7 _) → δ(_ R q2)          __001Y$00_

                                ↓
δ(q2 0) → δ(0 R q2)          __001Y$00_

                                 ↓
δ(q2 0) → δ(0 R q2)          __001Y$00_

                                  ↓
δ(q2 1) → δ(1 R q3)          __001Y$00_

                                   ↓
δ(q3 Y) → δ(Y R q3)          __001Y$00_

                                  ↓
δ(q3 $) → δ(_ L q8)          __001Y_00_

                                 ↓
δ(q8 Y) → δ(_ L q8)          __001__00_

                                ↓
δ(q8 1) → δ(_ L q8)          __00___00_

                               ↓
δ(q8 0) → δ(_ L q8)          __0____00_

                              ↓
δ(q8 0) → δ(_ L q8)          _______00_

                               ↓
δ(q8 _) → δ(_ R q9)          _______00_

------
No transition δ(q9 _) available. Halting.
ACCEPT
------